Problem Description

Aero-engine turbine blades are core equipment for ensuring national aerospace security, and their manufacturing process represents the peak of industrial technology.

On this day, in the center of the precision inspection laboratory, the chief structural analyst Xiao Lan is using high-precision sensors to continuously scan along the central axis of a turbine blade. The feedback data produced by the scan is converted into a sequence $A = (A_1, A_2, \dots, A_N)$ containing $N$ elements.

To evaluate the blade’s stability under extreme operating loads, Xiao Lan needs to compute a comprehensive strain index for this sequence. The first step of computing this index is to choose three split points $i, j, k$ (satisfying $1 \le i < j < k < N$), dividing the entire sequence into the following four consecutive and non-empty segments:

1. Segment 1: $A_1, \dots, A_i$.
2. Segment 2: $A_{i+1}, \dots, A_j$.
3. Segment 3: $A_{j+1}, \dots, A_k$.
4. Segment 4: $A_{k+1}, \dots, A_N$.

In the second step, compute the sum of all values in each segment, and take its absolute value. The sum of these four absolute values is defined as the comprehensive strain index under this partition:

$$|A_1 + \cdots + A_i| + |A_{i+1} + \cdots + A_j| + |A_{j+1} + \cdots + A_k| + |A_{k+1} + \cdots + A_N|$$

There are many possible choices of split points, and different plans will lead to different index results.

Now, please help Xiao Lan find a partition plan that maximizes the value of the comprehensive strain index.

Input Format

The first line contains a positive integer $N$, indicating the total number of feedback nodes collected in the scanned sequence.

The second line contains $N$ integers $A_1, A_2, \dots, A_N$, representing the elements of the sequence.

Output Format

Output one integer in a single line, representing the maximum comprehensive strain index that the sequence can achieve.

5
1 -1 -2 3 5

12

Hint

Constraints

For $30\%$ of the testdata, $4 \le N \le 100$.

For $60\%$ of the testdata, $4 \le N \le 400$.

For all testdata, $4 \le N \le 10^5$, $-10^9 \le A_i \le 10^9$.

Translated by ChatGPT 5