P15615 [ICPC 2021 Jakarta R] Maxdifficent Group

给定一个整数数组 $A_{1..N}$，其中 $N \geq 2$。需要将 $A$ 中的每个元素分配到一个组中，同时满足以下规则： - 每个元素恰好属于一个组。 - 如果 $A_{i}$ 和 $A_{j}$（其中 $i < j$）属于同一组，那么对于所有 $i \leq k \leq j$，$A_{k}$ 也与 $A_{i}$ 和 $A_{j}$ 属于同一组。 - 至少存在一对元素属于不同的组。 用 $G_{i}$ 表示元素 $A_{i}$ 的组编号。一个组的成本等于该组中所有 $A$ 的元素之和： $$\text{cost}(x) = \sum_{i \text{ 满足 } G_{i} = x} A_{i}$$ 两个不同的组编号 $G_{i}$ 和 $G_{j}$（其中 $G_{i} \neq G_{j}$）被称为 **相邻** 的，当且仅当对于所有 $i \leq k \leq j$，$G_{k}$ 要么是 $G_{i}$ 要么是 $G_{j}$。最后，两个组编号 $x$ 和 $y$ 的 $\text{diff}()$ 值定义为 $\text{cost}(x)$ 与 $\text{cost}(y)$ 之差的绝对值： $$\text{diff}(x, y) = |\text{cost}(x) - \text{cost}(y)|$$ 你的任务是找到一种分组方式，使得任意一对相邻组编号之间的 $\text{diff}()$ 值的最大值尽可能大；你只需要输出这个最大的 $\text{diff}()$ 值。 例如，设 $A_{1..4} = \{100, -30, -20, 70\}$。在此例中，有 $8$ 种将 $A$ 中每个元素分配到组的方式；其中一些如下所示： - $G_{1..4} = \{1, 2, 3, 4\}$。有 $3$ 对相邻的组编号，它们的 $\text{diff}()$ 值分别为： - $\text{diff}(1, 2) = |\text{cost}(1) - \text{cost}(2)| = |(100) - (-30)| = 130$， - $\text{diff}(2, 3) = |\text{cost}(2) - \text{cost}(3)| = |(-30) - (-20)| = 10$， - $\text{diff}(3, 4) = |\text{cost}(3) - \text{cost}(4)| = |(-20) - (70)| = 90$。 此分组方式中最大的 $\text{diff}()$ 值为 $130$。 - $G_{1..4} = \{1, 2, 2, 3\}$。有 $2$ 对相邻的组编号，它们的 $\text{diff}()$ 值分别为： - $\text{diff}(1, 2) = |\text{cost}(1) - \text{cost}(2)| = |(100) - (-30 + (-20))| = 150$， - $\text{diff}(2, 3) = |\text{cost}(2) - \text{cost}(3)| = |(-30 + (-20)) - (-20)| = 70$。 此分组方式中最大的 $\text{diff}()$ 值为 $150$。 其他 $6$ 种分组方式为：$G_{1..4} = \{1, 1, 1, 2\}$、$G_{1..4} = \{1, 1, 2, 2\}$、$G_{1..4} = \{1, 2, 2, 2\}$、$G_{1..4} = \{1, 1, 2, 2\}$、$G_{1..4} = \{1, 1, 2, 3\}$ 和 $G_{1..4} = \{1, 2, 3, 3\}$。在此例的所有可能分组方式中，从分组方式 $G_{1..4} = \{1, 2, 2, 3\}$ 可获得的最大 $\text{diff}()$ 值为 $150$。

输入第一行包含一个整数 $N$（$2 \leq N \leq 100\,000$），表示数组 $A$ 中元素的个数。下一行包含 $N$ 个整数 $A_{i}$（$-10^{6} \leq A_{i} \leq 10^{6}$），表示数组 $A$。

输出一行一个整数，表示通过某种分组方式所能获得的最大可能的 $\text{diff}()$ 值。

#### 样例 #2 解释 最大可能的 $\text{diff}()$ 值为 $46$，可通过分组方式 $G_{1..5} = \{1, 1, 1, 1, 2\}$ 获得。唯一一对相邻组编号的 $\text{diff}()$ 值为：$\text{diff}(1, 2) = 46$。 #### 样例 #3 解释 最大可能的 $\text{diff}()$ 值为 $70$，可通过分组方式 $G_{1..6} = \{1, 2, 2, 2, 3, 4\}$ 获得。任意两对相邻组编号的 $\text{diff}()$ 值分别为：$\text{diff}(1, 2) = 55$，$\text{diff}(2, 3) = 70$，$\text{diff}(3, 4) = 35$。 翻译由 DeepSeek 完成