Wesley a reçu un tableau de $N$ éléments $(a_1, a_2, \dots, a_N)$ pour Pâques, et il est impatient de le trier (de sorte que $a_1 \le a_2 \le \dots \le a_N$).

S'ennuyant, Wesley a décidé de se compliquer la tâche en ne s'autorisant à échanger deux éléments que si la différence absolue entre eux est inférieure ou égale à $K$. Notez que les éléments peuvent être n'importe où ; tant que leur différence absolue est inférieure ou égale à $K$, Wesley peut les échanger.

Malheureusement, Wesley s'est vite rendu compte qu'il pourrait ne pas être possible de trier le tableau. Il se demande alors : quelle est la valeur minimale de $K$ requise pour pouvoir trier le tableau ?

Entrée

La première ligne contient un entier $N$, le nombre d'éléments dans le tableau ($1 \le N \le 2 \cdot 10^5$).

La ligne suivante contient $N$ entiers $a_1, a_2, \dots, a_N$, le tableau lui-même ($1 \le a_i \le 10^{18}$).

Sortie

Affichez la valeur minimale de $K$ requise pour pouvoir trier le tableau. Si les éléments sont déjà triés, vous devez afficher 0.

Exemples

Entrée 1

8
1 4 4 2 7 14 12 10

Sortie 1

2