Il y a $n$ dominos de hauteur égale $h$ ($h_{\min} \le h \le h_{\max}$) placés en ligne droite. Le $i$-ième domino est placé à la position $a_i$.

Lobster et Mobster jouent au jeu suivant. Les joueurs jouent à tour de rôle en faisant tomber des dominos. À chaque tour, le joueur actuel choisit l'un des dominos et le fait tomber soit vers la gauche, soit vers la droite. Le domino tombe et peut éventuellement en faire tomber d'autres.

Un domino peut en faire tomber un autre si et seulement si la distance entre eux (différence de positions) est strictement inférieure à $h$. Par exemple, si un domino $i$ est à la position $a_i$ et qu'un domino $j$ situé à droite du domino $i$ est à la position $a_j$, et que $a_j - a_i < h$, alors faire tomber le domino $i$ vers la droite fera également tomber le domino $j$. Ensuite, le domino $j$ peut faire tomber le domino suivant, et ainsi de suite, jusqu'à ce que le dernier domino de la chaîne ne puisse plus atteindre le suivant.

Le jeu se termine lorsque tous les dominos sont tombés. Un joueur gagne s'il fait tomber le dernier domino, et un joueur perd si, à son tour, il ne peut pas faire tomber de domino car il n'en reste plus aucun à faire tomber.

Lobster joue en premier, ce qui lui donne un avantage. Par conséquent, avant le début de la partie, Mobster est autorisé à lancer un sortilège qui modifie la hauteur de tous les dominos de $h$ à un nombre arbitraire $h'$ choisi par Mobster dans l'intervalle $[h_{\min}, h_{\max}]$ (inclus).

Les joueurs jouent de manière optimale. Trouvez la hauteur minimale $h'$ qui permet à Mobster de gagner, ou déterminez si toute valeur de $h'$ conduit à une défaite de Mobster.

Entrée

La première ligne contient les entiers $n$, $h_{\min}$ et $h_{\max}$ ($1 \le n \le 10^5$, $1 \le h_{\min} \le h_{\max} \le 10^9$). La deuxième ligne contient $n$ entiers. Le $i$-ième d'entre eux est la position $a_i$ du $i$-ième domino ($-10^9 \le a_i \le 10^9$). Il est garanti que les positions de tous les dominos sont distinctes deux à deux.

Sortie

Affichez la hauteur minimale $h'$ qui permet à Mobster de gagner, ou affichez « -1 » si, pour toute valeur de $h'$ dans l'intervalle $[h_{\min}, h_{\max}]$, Mobster perd.

Exemples

Entrée 1

10 2 5
20 2 22 -4 0 -5 12 5 10 -9

Sortie 1

3