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

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

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

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

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

Во второй строке дано $n$ целых чисел $a_1$, $a_2$, $\dots$, $a_n$ $(0 <= a_i <= 10^5)$.

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

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

Примеры

Вход

7
4 1 2 3 1 3 2

Выход

1