Сік

Обмеження: 2 сек., 256 МіБ

На півфінал світу з програмування пройшли три команди з Львівського університету. Із цієї нагоди тренери команд придбали \(n\) пляшок соку та виставили їх в один ряд, \(i\)-та пляшка містить \(a_i\) грамів соку.

Перед головним тренером постала задача розділити пляшки на три неперервні відрізки так, щоб кожна команда отримала хоча б одну пляшку, та кожна пляшка належала рівно одній команді. Причому для того, щоб команди на змаганнях були в рівних умовах, різниця між найбільшою та найменшою кількістю випитого соку серед усіх команд має бути мінімально можливою.

Оскільки тренер уже скуштував березового соку, то розв’язати цю задачу він доручив вам.

Вхідні дані

У першому рядку задано ціле число \(n\) — кількість пляшок із соком.

У наступному рядку задано \(n\) чисел \(a_i\) — місткість \(i\)-ої пляшки в грамах.

Вихідні дані

В одному рядку виведіть ціле число — мінімальну можливу різницю між найбільшою та найменшою кількостями випитого соку в грамах.

Обмеження

У 10 тестах:

\(3 \le n \le 2\cdot10^3\),

\(1 \le a_i \le 10^6\),

у всіх решту тестах:

\(3 \le n \le 10^5\),

\(1 \le a_i \le 10^9\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 1 3 2 4 1 3 7	2

Примітки

У прикладі оптимально розділити пляшки на відрізки [1, 3, 2], [4, 1, 3], [7]. Тоді перша команда вип’є сумарно 6 грамів соку, друга — 8, третя — 7. Різниця між найбільшим та найменшим значеннями — \(8 - 6 = 2\).