Maxdifficent Group

정수 배열 $A_{1..N}$이 주어진다. 단, $N \ge 2$이다. 배열의 각 원소를 다음 규칙을 지키면서 그룹에 배정한다.

• 각 원소는 정확히 하나의 그룹에 속한다.
• $i < j$인 $A_i$와 $A_j$가 같은 그룹에 속하면, $i \le k \le j$인 모든 $A_k$도 같은 그룹에 속한다.
• 서로 다른 그룹에 속한 원소 쌍이 적어도 하나 있다.

$G_i$를 $A_i$의 그룹 ID라고 하자. 그룹의 비용은 그 그룹에 배정된 $A$의 원소를 모두 더한 값이다.

$\text{cost}(x) = \sum_{i: G_i = x} A_i$

서로 다른 두 그룹 ID $G_i$와 $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}()$ 값의 최댓값이 가장 커지도록 그룹을 배정한다. 이 최댓값만 출력하면 된다.

예를 들어 $A_{1..4} = \{100, -30, -20, 70\}$이면 그룹을 배정하는 방법은 8가지이다. 배정 $G_{1..4} = \{1, 2, 2, 3\}$이면 가장 큰 $\text{diff}()$ 값은 150이다.

첫 줄에 $A$의 원소 개수 $N$ ($2 \le N \le 100{,}000$)이 주어진다. 다음 줄에는 $N$개의 정수 $A_i$ ($-10^6 \le A_i \le 10^6$)가 주어진다.

모든 그룹 배정에 대해 얻을 수 있는 $\text{diff}()$ 값의 최댓값을 한 줄에 출력한다.