Сік

Limits: 2 sec., 256 MiB

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

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

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

Input

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

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

Output

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

Constraints

У 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\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 1 3 2 4 1 3 7	2

Notes

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