给定一个包含 $N$ 个整数的数组 $A_{1..N}$，其中 $N \ge 2$。数组 $A$ 中的每个元素都需要被分配到一个组中，并满足以下规则：
- 每个元素恰好属于一个组。
- 如果 $A_i$ 和 $A_j$（其中 $i < j$）属于同一个组，那么对于所有 $i \le k \le j$，元素 $A_k$ 也必须属于与 $A_i$ 和 $A_j$ 相同的组。
- 至少存在一对属于不同组的元素。
令 $G_i$ 表示元素 $A_i$ 的组 ID。一个组的代价等于该组中所有元素之和： $$\text{cost}(x) = \sum_{i \text{ s.t. } G_i=x} A_i$$
两个不同的组 ID $G_i$ 和 $G_j$（其中 $G_i \neq G_j$）被称为是相邻的，当且仅当对于所有 $i \le k \le j$，都有 $G_k$ 等于 $G_i$ 或 $G_j$。最后，两个组 ID $x$ 和 $y$ 的 $\text{diff}()$ 值定义为它们代价的绝对差： $$\text{diff}(x, y) = |\text{cost}(x) - \text{cost}(y)|$$
你的任务是找到一种分组方案，使得任意一对相邻组 ID 之间的最大 $\text{diff}()$ 值尽可能大；你只需要输出这个最大的 $\text{diff}()$ 值。
例如，设 $A_{1..4} = \{100, -30, -20, 70\}$。在这个例子中，将 $A$ 中的每个元素分配到组中有 8 种方式；其中一些如下所示：
$G_{1..4} = \{1, 2, 3, 4\}$。有 3 对相邻的组 ID，它们的 $\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 对相邻的组 ID，它们的 $\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 \le N \le 100\,000$)，表示数组 $A$ 中元素的个数。下一行包含 $N$ 个整数 $A_i$ ($-10^6 \le A_i \le 10^6$)，表示数组 $A$。
输出格式
输出一行一个整数，表示通过分组方案可以获得的最大 $\text{diff}()$ 值。
样例
输入 1
4 100 -30 -20 50
输出 1
150
说明 1
这是题目描述中的例子。
输入 2
5 12 7 4 32 9
输出 2
46
说明 2
可以通过分组方案 $G_{1..5} = \{1, 1, 1, 1, 2\}$ 获得 46 的最大 $\text{diff}()$ 值。唯一相邻组 ID 的 $\text{diff}()$ 值为：$\text{diff}(1, 2) = 45$。
输入 3
6 -5 10 -5 45 -20 15
输出 3
70
说明 3
可以通过分组方案 $G_{1..6} = \{1, 2, 2, 2, 3, 4\}$ 获得 70 的最大 $\text{diff}()$ 值。任意两个相邻组 ID 的 $\text{diff}()$ 值为：$\text{diff}(1, 2) = 55, \text{diff}(2, 3) = 70$ 以及 $\text{diff}(3, 4) = 35$。