Задача: Радость Громозеки
Громозека имеет последовательность целых чисел 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·105). Во второй строке записано N целых чисел Ai (1 <= Ai <= 109).
Выходные данные
Выведите на экран минимально возможную абсолютную разницу между максимумом и минимумом между 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 |
|
Ваш ответ: