Задача . Радость Громозеки

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

Выходные данные
Выведите на экран минимально возможную абсолютную разницу между максимумом и минимумом между 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