Maxdifficent Group

문제

Given an array of integers $A_{\mathrm{1..}N}A\_\{1..N\}$ where N ≥ 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}A\_i$ and $A_{j}A\_j$ where belongs to the same group, then $A_{k}A\_k$ where i ≤ k ≤ j also belongs to the same group as $A_{i}A\_i$ and $A_{j}A\_j$.
• There is at least one pair of elements that belong to a different group.

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

$$\text{cost}(x)=\sum _{\text{i s.t. }{G}_i=x}{A}_i\backslash text\{cost\}(x)\; =\; \backslash sum\_\{\backslash text\{i\; s.t.\; \}G\_i\; =\; x\}\{A\_i\}$$

Two different group IDs, $G_{i}G\_i$ and $G_{j}G\_j$ (where $G_i\mathrm{\ne }{G}_{j}G\_i\; \backslash ne\; G\_j$), are adjacent if and only if $G_{k}G\_k$ is either $G_{i}G\_i$ or $G_{j}G\_j$ for every i ≤ k ≤ j. Finally, the $\text{diff}()\backslash text\{diff\}()$ value of two group IDs $xx$ and $yy$ is defined as the absolute difference between $\text{cost}(x)\backslash text\{cost\}(x)$ and $\text{cost}(y)\backslash 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}()\backslash text\{diff\}()$ value between any pair of adjacent group IDs is maximized; you only need to output the largest $\text{diff}()\backslash text\{diff\}()$ value.

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

• $G_{\mathrm{1..4}}=\{1,2,3,4\}G\_\{1..4\}\; =\; \backslash \{1,\; 2,\; 3,\; 4\backslash \}$. There are $33$ pairs of group IDs that are adjacent and their $\text{diff}()\backslash 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}()\backslash text\{diff\}()$ value in this group assignment is $130130$.
• $G_{\mathrm{1..4}}=\{1,2,2,3\}G\_\{1..4\}\; =\; \backslash \{1,\; 2,\; 2,\; 3\backslash \}$. There are $22$ pairs of group IDs that are adjacent and their $\text{diff}()\backslash 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}()\backslash text\{diff\}()$ value in this group assignment is $150150$.

The other $66$ group assignments are: $G_{\mathrm{1..4}}=\{1,1,1,2\}G\_\{1..4\}\; =\; \backslash \{1,\; 1,\; 1,\; 2\backslash \}$, $G_{\mathrm{1..4}}=\{1,1,2,2\}G\_\{1..4\}\; =\; \backslash \{1,\; 1,\; 2,\; 2\backslash \}$, $G_{\mathrm{1..4}}=\{1,2,2,2\}G\_\{1..4\}\; =\; \backslash \{1,\; 2,\; 2,\; 2\backslash \}$, $G_{\mathrm{1..4}}=\{1,1,2,2\}G\_\{1..4\}\; =\; \backslash \{1,\; 1,\; 2,\; 2\backslash \}$, $G_{\mathrm{1..4}}=\{1,1,2,3\}G\_\{1..4\}\; =\; \backslash \{1,\; 1,\; 2,\; 3\backslash \}$, and $G_{\mathrm{1..4}}=\{1,2,3,3\}G\_\{1..4\}\; =\; \backslash \{1,\; 2,\; 3,\; 3\backslash \}$. Among all possible group assignments in this example, the maximum largest $\text{diff}()\backslash text\{diff\}()$ that can be obtained is $150150$ from the group assignment $G_{\mathrm{1..4}}=\{1,2,2,3\}G\_\{1..4\}\; =\; \backslash \{1,\; 2,\; 2,\; 3\backslash \}$.

입력

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

출력

Output contains an integer in a line representing the maximum possible largest $\text{diff}()\backslash 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