Громозека имеет последовательность целых чисел
A длины
N. Он сделает три среза в последовательности
A и разделит ее на четыре (непустые) смежные подпоследовательности
B,
C,
D и
E. Положения срезов он выбирает произвольно. Пусть
P,
Q,
R,
S - суммы элементов в
B,
C,
D,
E соответственно. Громозека будет счастлив, когда абсолютная разница между максимумом и минимумом между
P,
Q,
R,
S будет минимальной. Найдите минимально возможную абсолютную разницу между максимумом и минимумом между
P,
Q,
R,
S.
Входные данные
В первой строке записано целое число
N (1 <=
N <= 2·10
5). Во второй строке записано
N целых чисел
Ai (1 <=
Ai <= 10
9).
Выходные данные
Выведите на экран минимально возможную абсолютную разницу между максимумом и минимумом между
P,
Q,
R,
S.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
5
3 2 4 1 2 |
2 |
Если разделить A на B, C, D, E = (3), (2), (4), (1,2), то P = 3, Q = 2, R = 4, S = 1 + 2 = 3.
Здесь максимум и минимум среди P, Q, R, S равны 4 и 2, с абсолютной разницей 2.
Мы не можем сделать абсолютную разницу между максимумом и минимумом меньше 2, поэтому ответ - 2. |
| 2 |
10
10 71 84 33 6 47 23 25 52 64 |
36 |
|
| 3 |
7
1 2 3 1000000000 4 5 6 |
999999994 |
|