题目描述

Given an array of integers $A_{1..N}$ where $N \geq 2$. Each element in $A$ should be assigned into a group while satisfying the following rules.

• Each element belongs to exactly one group.
• If $A_{i}$ and $A_{j}$ where $i < j$ belongs to the same group, then $A_{k}$ where $i \leq k \leq j$ also belongs to the same group as $A_{i}$ and $A_{j}$.
• There is at least one pair of elements that belong to a different group.

Let $G_{i}$ denotes the group ID of element $A_{i}$. The cost of a group is equal to the sum of all elements in $A$ that belong to that group.

$$\text{cost}(x) = \sum_{i \text{ s.t. } G_{i} = x} A_{i} $$

Two different group IDs, $G_{i}$ and $G_{j}$ (where $G_{i} \neq G_{j}$), are adjacent if and only if $G_{k}$ is either $G_{i}$ or $G_{j}$ for every $i \leq k \leq j$. Finally, the $\text{diff}()$ value of two group IDs $x$ and $y$ is defined as the absolute difference between $\text{cost}(x)$ and $\text{cost}(y)$.

$$\text{diff}(x, y) = |\text{cost}(x) - \text{cost}(y)| $$

Your task in this problem is to find a group assignment such that the largest $\text{diff}()$ value between any pair of adjacent group IDs is maximized; you only need to output the largest $\text{diff}()$ value.

For example, let $A_{1..4} = \{100, -30, -20, 70\}$. There are $8$ ways to assign each element in $A$ into a group in this example; some of them are shown as follows.

• $G_{1..4} = \{1, 2, 3, 4\}$. There are $3$ pairs of group IDs that are adjacent and their $\text{diff}()$ values are:
  • $\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$, and
  • $\text{diff}(3, 4) = |\text{cost}(3) - \text{cost}(4)| = |(-20) - (70)| = 90$.

The largest $\text{diff}()$ value in this group assignment is $130$.

• $G_{1..4} = \{1, 2, 2, 3\}$. There are $2$ pairs of group IDs that are adjacent and their $\text{diff}()$ values are:
  • $\text{diff}(1, 2) = |\text{cost}(1) - \text{cost}(2)| = |(100) - (-30 + (-20))| = 150$, and
  • $\text{diff}(2, 3) = |\text{cost}(2) - \text{cost}(3)| = |(-30 + (-20)) - (-20)| = 70$.

The largest $\text{diff}()$ value in this group assignment is $150$.

The other $6$ group assignments are: $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\}$, and $G_{1..4} = \{1, 2, 3, 3\}$. Among all possible group assignments in this example, the maximum largest $\text{diff}()$ that can be obtained is $150$ from the group assignment $G_{1..4} = \{1, 2, 2, 3\}$.

输入格式

Input begins with a line containing an integer $N$ ($2 \leq N \leq 100\,000$) representing the number of elements in array $A$. The next line contains $N$ integers $A_{i}$ ($-10^{6} \leq A_{i} \leq 10^{6}$) representing the array $A$.

输出格式

Output contains an integer in a line representing the maximum possible largest $\text{diff}()$ that can be obtained from a group assignment.

4
100 -30 -20 50

150

5
12 7 4 32 9

46

6
-5 10 -5 45 -20 15

70

提示

Explanation for the sample input/output #2

The maximum possible largest $\text{diff}()$ of $46$ can be obtained from the group assignment $G_{1..5} = \{1, 1, 1, 1, 2\}$. The $\text{diff}()$ value of the only adjacent group IDs is: $\text{diff}(1, 2) = 46$.

Explanation for the sample input/output #3

The maximum possible largest $\text{diff}()$ of $70$ can be obtained from the group assignment $G_{1..6} = \{1, 2, 2, 2, 3, 4\}$. The $\text{diff}()$ values of any two adjacent group IDs are: $\text{diff}(1, 2) = 55$, $\text{diff}(2, 3) = 70$, and $\text{diff}(3, 4) = 35$.