Avec le petit Kostek, vous construisez des tours en cubes. Vous avez déjà construit $n$ tours alignées, la $i$-ème étant de hauteur $h_i$. Maintenant, Kostek veut fixer une frontière entre ses tours et les vôtres. Les tours à gauche de la frontière appartiendront à Kostek, et les tours restantes à droite seront à vous. Chacun de vous doit avoir au moins une tour.
Vous êtes sur le point de passer au jeu suivant, qui commence par le placement, par chacun d'entre vous, d'un éclaireur sur sa tour la plus haute. Le jeu ne sera pas amusant si les éclaireurs se tiennent à des hauteurs complètement différentes. Par conséquent, vous devez proposer le partage le plus équitable possible : choisissez la frontière de manière à minimiser la valeur absolue de la différence entre la hauteur de la plus haute tour de Kostek et celle de la vôtre. Affichez cette différence minimale.
Entrée
La première ligne contient un entier $n$ ($2 \le n \le 300\,000$), désignant le nombre de tours.
La deuxième ligne contient $n$ entiers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), désignant les hauteurs des tours consécutives de gauche à droite.
Sortie
Affichez un entier – la plus petite différence de hauteur possible entre la plus haute de vos tours et la plus haute des tours de Kostek.
Exemples
Entrée 1
3 200 333 100
Sortie 1
133
Entrée 2
5 5 2 4 1 5
Sortie 2
0
Entrée 3
6 5 1 4 4 2 3
Sortie 3
1
Note
Dans le premier test, Kostek devrait placer la frontière entre les deux premières tours. Il a alors une tour de hauteur $200$, tandis que vous avez des tours de hauteurs $333$ et $100$. Vos tours les plus hautes sont de hauteurs $200$ et $333$, le résultat est donc $133$. Il n'est pas possible d'obtenir une différence plus petite.
Dans le deuxième test, n'importe quel partage donne une différence de $0$.
Dans le troisième test, Kostek devrait placer la frontière après la première, la deuxième ou la troisième tour. La différence demandée vaut alors $|5 - 4| = 1$. Le schéma ci-dessous illustre l'une de ces possibilités optimales :
