Mamy $n$ kostek domina o równej wysokości $h$ ($h_{\min} \le h \le h_{\max}$), ustawionych w linii prostej. $i$-ta kostka znajduje się na pozycji $a_i$.
Lobster i Mobster grają w następującą grę. Gracze na zmianę przewracają kostki domina. W każdej turze obecny gracz wybiera jedną z kostek i przewraca ją w lewo lub w prawo. Kostka upada i może przewrócić kolejne kostki.
Jedna kostka może przewrócić drugą wtedy i tylko wtedy, gdy odległość między nimi (różnica pozycji) jest ściśle mniejsza niż $h$. Na przykład, jeśli kostka $i$ znajduje się na pozycji $a_i$, a kostka $j$ znajduje się na prawo od kostki $i$ na pozycji $a_j$, oraz $a_j - a_i < h$, to przewrócenie kostki $i$ w prawo spowoduje również przewrócenie kostki $j$. Następnie kostka $j$ może przewrócić kolejną kostkę i tak dalej, aż ostatnia kostka w łańcuchu nie będzie w stanie dosięgnąć następnej.
Gra kończy się, gdy wszystkie kostki zostaną przewrócone. Gracz wygrywa, jeśli przewróci ostatnią kostkę, a gracz przegrywa, jeśli w swojej turze nie może przewrócić żadnej kostki, ponieważ wszystkie pozostałe są już przewrócone.
Lobster wykonuje ruch jako pierwszy, co daje mu przewagę. Dlatego przed rozpoczęciem gry Mobster może rzucić zaklęcie, które zmienia wysokość wszystkich kostek z $h$ na dowolną liczbę $h'$ wybraną przez Mobstera z zakresu $[h_{\min}, h_{\max}]$ (włącznie).
Gracze grają optymalnie. Znajdź minimalną wysokość kostek $h'$, która zapewnia Mobsterowi zwycięstwo, lub określ, że każda wartość $h'$ prowadzi do przegranej Mobstera.
Wejście
Pierwsza linia zawiera liczby całkowite $n$, $h_{\min}$ oraz $h_{\max}$ ($1 \le n \le 10^5$, $1 \le h_{\min} \le h_{\max} \le 10^9$).
Druga linia zawiera $n$ liczb całkowitych. $i$-ta z nich to pozycja $a_i$ $i$-tej kostki ($-10^9 \le a_i \le 10^9$). Gwarantuje się, że pozycje wszystkich kostek są parami różne.
Wyjście
Wypisz minimalną wysokość $h'$, która zapewnia Mobsterowi zwycięstwo, lub wypisz „-1”, jeśli dla każdej wartości $h'$ z zakresu $[h_{\min}, h_{\max}]$ Mobster przegrywa.
Przykład
Wejście 1
10 2 5 20 2 22 -4 0 -5 12 5 10 -9
Wyjście 1
3