← 返回题目列表

AtCoder · arc196_a

A. 相邻删除

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你一个长度-N 序列 A = (A_1, A_2, \ldots, A_N).

您将重复执行以下操作,直到序列的长度达到最大 1:选择两个相邻的数字并将它们从序列中删除。

一次操作获得的分数是两个所选数字的绝对差。

找出可能获得的最大总分。

约束

  • 2 \le N \le 3 \times 10^5
  • 1 \le A_i \le 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印获得的最大可能总分。


示例输入 1

4
1 2 5 3

示例输出 1

5

首先,删除 A_2 和 A_3。得到的分数是 |A_2 - A_3| = 3.

接下来,删除 A_1 和 A_4。请注意,由于之前的操作,这两个数字现在相邻。得到的分数是 |A_1 - A_4| = 2.

因此,获得的总分是 5.

总分不可能达到 6 或更大,因此打印 5.


示例输入 2

7
3 1 4 1 5 9 2

示例输出 2

14

示例输入 3

5
1 1 1 1 1

示例输出 3

0