Задається послідовність цілих чисел ~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