Wesley otrzymał na Wielkanoc tablicę $N$ elementów $(a_1, a_2, \dots, a_N)$ i bardzo chce ją posortować (tak, aby $a_1 \le a_2 \le \dots \le a_N$).

Znudzony Wesley postanowił utrudnić sobie zadanie, pozwalając na zamianę miejscami dwóch elementów tylko wtedy, gdy wartość bezwzględna różnicy między nimi jest mniejsza lub równa $K$. Zauważ, że elementy mogą znajdować się w dowolnym miejscu; dopóki wartość bezwzględna ich różnicy jest mniejsza lub równa $K$, Wesley może je zamienić.

Niestety, Wesley szybko zdał sobie sprawę, że posortowanie tablicy może nie być możliwe. Zastanawia się więc: jaka jest minimalna wartość $K$ wymagana, aby móc posortować tablicę?

Wejście

W pierwszej linii znajduje się liczba całkowita $N$, określająca liczbę elementów w tablicy ($1 \le N \le 2 \cdot 10^5$).

W drugiej linii znajduje się $N$ liczb całkowitych $a_1, a_2, \dots, a_N$, czyli elementy tablicy ($1 \le a_i \le 10^{18}$).

Wyjście

Wypisz minimalną wartość $K$ wymaganą, aby móc posortować tablicę. Jeśli elementy są już posortowane, należy wypisać 0.

Przykład

Wejście 1

8
1 4 4 2 7 14 12 10

Wyjście 1

2