AT_codequeen2023_final_e Good Partition

给定一个长度为 $N$ 的数列 $A = (a_1, a_2, \ldots, a_N)$。 现在考虑将该数列分割为若干个连续且非空的子序列 $B_1, B_2, \ldots, B_K$。例如，当 $A = (5, -3, 6, 2, 4)$ 时，$A$ 的一些分割方式如下： - $B_1 = (5),\ B_2 = (-3, 6, 2),\ B_3 = (4)$ - $B_1 = (5, -3),\ B_2 = (6, 2, 4)$ - $B_1 = (5, -3, 6, 2, 4)$ 对于每个子序列 $B_i$，定义其**得分** $S(B_i)$ 为其中最大值与最小值之差，即 $S(B_i) = \max B_i - \min B_i$。 请你求出，将 $A$ 最优分割后，所有子序列的得分和 $\sum_i S(B_i)$ 的最大可能值。

输入以如下形式从标准输入给出。 > $N\ a_1\ a_2\ \ldots\ a_N$

输出子序列得分和的最大值。

## 样例解释 1 $B_1 = (1, 2, 2, 4),\ B_2 = (5, 2, 3),\ B_3 = (4, 1)$ 是一种最优分割方式。 - $S(B_1) = 4 - 1 = 3$ - $S(B_2) = 5 - 2 = 3$ - $S(B_3) = 4 - 1 = 3$ 因此，得分和为 $9$，这是答案。 ## 数据范围 - 所有输入均为整数 - $1 \leq N \leq 200{,}000$ - $|a_i| \leq 10^9\ (1 \leq i \leq N)$ 由 ChatGPT 5 翻译