Уэсли получил на Пасху массив из $N$ элементов $(a_1, a_2, \dots, a_N)$ и хочет отсортировать его (так, чтобы $a_1 \le a_2 \le \dots \le a_N$).

От скуки Уэсли решил усложнить себе задачу: он разрешил себе менять местами два элемента только в том случае, если их абсолютная разность меньше или равна $K$. Заметьте, что элементы могут находиться в любых позициях; если их абсолютная разность меньше или равна $K$, Уэсли может поменять их местами.

К сожалению, Уэсли быстро понял, что отсортировать массив таким образом может быть невозможно. Теперь он задается вопросом: какое минимальное значение $K$ необходимо, чтобы отсортировать массив?

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

Первая строка содержит целое число $N$ — количество элементов в массиве ($1 \le N \le 2 \cdot 10^5$).

Вторая строка содержит $N$ целых чисел $a_1, a_2, \dots, a_N$ — сам массив ($1 \le a_i \le 10^{18}$).

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

Выведите минимальное значение $K$, необходимое для того, чтобы отсортировать массив. Если элементы уже отсортированы, выведите 0.

Примеры

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

8
1 4 4 2 7 14 12 10

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

2