Областная олимпиада по информатике 2020 года за 10 класс | Казахстанские олимпиады

Задача D. Разделение массива

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

У Тимы есть три младших брата: Батыр, Димаш и Есмахан. Тима решил дать им массив aa из nn целых чисел, чтобы развлечь их. Он хочет разделить массив на три непустых частей и раздать своим братьям, чтобы каждое число было ровно в одной части. Все числа одной части должны идти подряд в массиве. Пусть AA - сумма чисел в первой части, BB - сумма чисел во второй, CC - сумма в третьей. Чтобы братья не ругались, Тима хочет минимизировать max(A, B, C) - min(A, B, C). Найдите минимальное значение max(A, B, C) - min(A, B, C).

Формат входного файла

В первой строке дано одно целое число nn (3<=n<=3105)(3 <= n <= 3 * 10^5).

Во второй строке дано nn целых чисел a1a_1, a2a_2, \dots, ana_n (0<=ai<=105)(0 <= a_i <= 10^5).

Формат выходного файла

Выведите одно целое число — ответ на задачу.

Примеры

Вход

7
4 1 2 3 1 3 2

Выход

1