Razem z małym Kostkiem budujecie wieże z klocków. Zbudowaliście już $n$ wież w rzędzie, z których $i$-ta ma wysokość $h_i$. Teraz Kostek chce wyznaczyć granicę między swoimi a Twoimi wieżami. Wieże na lewo od granicy będą należały do Kostka, a pozostałe wieże po prawej stronie będą Twoje. Każde z was musi mieć co najmniej jedną wieżę.

Za chwilę przejdziecie do kolejnej zabawy, która zaczyna się od tego, że każde z was stawia zwiadowcę na swojej najwyższej wieży. Zabawa nie będzie udana, jeśli zwiadowcy będą stali na zupełnie różnych wysokościach. Dlatego powinieneś zaproponować jak najbardziej sprawiedliwy podział – wybierz granicę tak, aby zminimalizować wartość bezwzględną różnicy między wysokością najwyższej wieży Kostka a Twojej. Wypisz tę minimalną różnicę.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($2 \le n \le 300\,000$), oznaczającą liczbę wież.

Drugi wiersz zawiera $n$ liczb całkowitych $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), oznaczających wysokości kolejnych wież od lewej do prawej.

Wyjście

Wypisz jedną liczbę całkowitą – najmniejszą możliwą różnicę wysokości między najwyższą z Twoich wież a najwyższą z wież Kostka.

Przykłady

Wejście 1

3
200 333 100

Wyjście 1

133

Wejście 2

5
5 2 4 1 5

Wyjście 2

0

Wejście 3

6
5 1 4 4 2 3

Wyjście 3

1

Uwaga

W pierwszym teście Kostek powinien ustawić granicę między pierwszymi dwiema wieżami. Ma wtedy wieżę o wysokości $200$, podczas gdy Ty masz wieże o wysokościach $333$ i $100$. Wasze najwyższe wieże mają wysokości $200$ i $333$, więc wynikiem jest $133$. Nie da się uzyskać mniejszej różnicy.

W drugim teście każdy podział daje różnicę równą $0$.

W trzecim teście Kostek powinien ustawić granicę za pierwszą, drugą lub trzecią wieżą. Szukana różnica wynosi wtedy $|5 - 4| = 1$. Poniższy rysunek przedstawia jedną z tych optymalnych możliwości: