AT_xmascontest2015_g Good Sequence

うなぎ在圣诞节收到了来自サンタうさぎ的一串数列 $A=\{A_1,A_2,...,A_N\}$。 うなぎ打算从数列 $A$ 中删除若干个（可以为 $0$ 个）元素，来构造一个“良好数列”。数列 $x$ 被称为良好数列，当且仅当满足以下性质： - 对于所有 $i\ (2\leq i\leq |x|-1)$，$x_i$ 不是 $x_{i-1},\ x_i,\ x_{i+1}$ 三者中的中位数。 例如，$x=\{2,1,3,2\}$ 和 $x=\{2,1,2\}$ 满足条件，但 $x=\{1,2,3\}$ 和 $x=\{1,1,3,2\}$ 不满足条件。另外，长度小于 $3$ 的数列也满足条件。 数列 $x$ 的“凹凸度”定义为相邻元素差的绝对值之和。用公式表示为 $Σ_{1\leq i\leq |x|-1}|x_i-x_{i+1}|$。 请你求出可以通过删除 $A$ 中若干元素得到的良好数列的凹凸度的最大值。

输入通过标准输入按以下格式给出。 > $N$ > $A_1\ A_2\ ...\ A_N$ - 第 $1$ 行为整数 $N$，表示数列 $A$ 的长度，$2\leq N\leq 10^5$。 - 第 $2$ 行包含 $N$ 个用空格分隔的整数，第 $i$ 个为 $A_i$，满足 $0\leq A_i\leq 10^9$。

请输出可以通过删除 $A$ 中若干元素得到的良好数列的凹凸度的最大值。输出末尾需换行。

## 部分分 本题设有部分分。 - 对于 $N\leq 1,000$ 的数据集，答对可得 $20$ 分。 - 对于无附加限制的数据集，答对可得 $80$ 分（与上述 $20$ 分无关）。 ## 样例解释 1 例如，删除第 $1$ 和第 $4$ 个元素后，得到 $\{1,3,1\}$，其凹凸度为 $4$。 由 ChatGPT 4.1 翻译