Задається послідовність цілих чисел \(A\) довжиною \(N\).

Розіб'ємо дану послідовність на чотири суміжних непорожніх підпослівностей. Позначимо їх суми \(P,Q,R,S\).

Ваша задача розбити послідовність так, щоб абсолютна різниця між максимальною та мінімальною сумами з \(P,Q,R,S\) була мінімальна. Знайдіть цю різницю.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\) \((4 \le N \le 2 \cdot 10^5)\)

Наступний рядок містить цілі числа \(A_i\) \((1 \le A_i \le 10^9)\), які розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукану мінімальну абсолютну різницю між максимальною та мінімальною сумами серед \(P,Q,R,S\)

Приклад вхідних даних

5
3 2 4 1 2

Приклад вихідних даних

2