26862번 - Maxdifficent Group 다국어

문제

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.

제한

힌트