Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Алгоритмы обработки

Условие задачи  
ID 38716
Радость Громозеки
Темы: Массивы    Алгоритмы обработки   

Громозека имеет последовательность целых чисел 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 \cdot 10^5\)). Во второй строке записано N целых чисел Ai (\(1<=A_i<=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