Вместе с маленьким Костеком вы строите башни из кубиков. Вы уже построили $n$ башен в ряд, причём высота $i$-й башни равна $h_i$. Теперь Костек хочет провести границу между своими и вашими башнями. Башни слева от границы достанутся Костеку, а оставшиеся башни справа будут вашими. У каждого из вас должна быть хотя бы одна башня.

Вы собираетесь перейти к следующей игре, которая начинается с того, что каждый из вас ставит разведчика на свою самую высокую башню. Игра будет неинтересной, если разведчики окажутся на совершенно разной высоте. Поэтому вам следует предложить как можно более справедливое разделение — выбрать границу так, чтобы минимизировать абсолютную величину разности между высотой самой высокой башни Костека и вашей. Выведите эту минимальную разность.

Входные данные

Первая строка содержит целое число $n$ ($2 \le n \le 300\,000$), обозначающее количество башен.

Вторая строка содержит $n$ целых чисел $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), обозначающих высоты последовательных башен слева направо.

Выходные данные

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

Примеры

Входные данные 1

3
200 333 100

Выходные данные 1

133

Входные данные 2

5
5 2 4 1 5

Выходные данные 2

0

Входные данные 3

6
5 1 4 4 2 3

Выходные данные 3

1

Примечание

В первом примере Костеку следует провести границу между первыми двумя башнями. Тогда у него будет башня высоты $200$, а у вас — башни высоты $333$ и $100$. Ваши самые высокие башни имеют высоты $200$ и $333$, поэтому ответ равен $133$. Меньшую разность получить невозможно.

Во втором примере любое разделение даёт разность $0$.

В третьем примере Костеку следует провести границу после первой, второй или третьей башни. Тогда искомая разность равна $|5 - 4| = 1$. На рисунке ниже показан один из таких оптимальных вариантов: