시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB55484285.714%

문제

Given an array of integers $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$ and $A_j$ where $i < j$ belongs to the same group, then $A_k$ where $i ≤ k ≤ 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_{\text{i s.t. }G_i = x}{A_i}$$

Two different group IDs, $G_i$ and $G_j$ (where $G_i \ne G_j$), are adjacent if and only if $G_k$ is either $G_i$ or $G_j$ for every $i ≤ k ≤ 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 ≤ N ≤ 100\,000$) representing the number of elements in array $A$. The next line contains $N$ integers $A_i$ ($-10^6 ≤ A_i ≤ 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.

예제 입력 1

4
100 -30 -20 50

예제 출력 1

150

This is the example from the problem statement.

예제 입력 2

5
12 7 4 32 9

예제 출력 2

46

The maximum possible largest $\text{diff}()$ of $45$ 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) = 45$.

예제 입력 3

6
-5 10 -5 45 -20 15

예제 출력 3

70

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$.