Gromozek has a sequence of integers
A of length
N. It will make three slices in the
A sequence and split it into four (non-empty) contiguous subsequences
B,
C,
D > and
E. He chooses the positions of the slices arbitrarily. Let
P,
Q,
R,
S be the sums of elements in
B, < code>C,
D,
E respectively. Gromozeka will be happy when the absolute difference between the maximum and minimum between
P,
Q,
R,
S minimum. Find the smallest possible absolute difference between the maximum and minimum between
P,
Q,
R,
S.
Input
The first line contains an integer
N (
\(1<=N<=2 \cdot 10^5\)). The second line contains
N integers
Ai (
\(1<=A_i<=10 ^9\)).
Imprint
Print the smallest possible absolute difference between the maximum and minimum between
P,
Q,
R,
S.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
5
3 2 4 1 2
| 2 |
If we divide A by B, C, D, E = (3), (2), (4), (1,2), then P = 3, Q = 2, R = 4, S = 1 + 2 = 3.
Here the maximum and minimum among P, Q, R, S are 4 and 2, with an absolute difference of 2.
We can't make the absolute difference between the maximum and minimum less than 2, so the answer is 2. |
| 2 |
10
10 71 84 33 6 47 23 25 52 64
| 36 |
|
| 3 |
7
1 2 3 1000000000 4 5 6
| 999999994 |
|