Rakennat pikku Kostekin kanssa torneja palikoista. Olette jo rakentaneet riviin $n$ tornia, joista $i$:nnen korkeus on $h_i$. Nyt Kostek haluaa asettaa rajan hänen ja sinun torniesi välille. Rajan vasemmalla puolella olevat tornit kuuluvat Kostekille ja oikealla puolella olevat loput tornit sinulle. Kummallakin teistä täytyy olla vähintään yksi torni.

Olette juuri siirtymässä seuraavaan leikkiin, joka alkaa sillä, että kumpikin teistä asettaa tiedustelijan korkeimman torninsa huipulle. Leikki ei ole hauskaa, jos tiedustelijat seisovat täysin eri korkeuksilla. Siksi sinun kannattaa ehdottaa mahdollisimman reilua jakoa – valitse raja siten, että Kostekin korkeimman tornin ja sinun korkeimman tornisi korkeuksien erotuksen itseisarvo on mahdollisimman pieni. Tulosta tämä pienin mahdollinen erotus.

Syöte

Ensimmäisellä rivillä on kokonaisluku $n$ ($2 \le n \le 300\,000$), joka ilmaisee tornien lukumäärän.

Toisella rivillä on $n$ kokonaislukua $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), jotka ilmaisevat peräkkäisten tornien korkeudet vasemmalta oikealle.

Tuloste

Tulosta yksi kokonaisluku – pienin mahdollinen korkeusero sinun korkeimman tornisi ja Kostekin korkeimman tornin välillä.

Esimerkit

Syöte 1

3
200 333 100

Tuloste 1

133

Syöte 2

5
5 2 4 1 5

Tuloste 2

0

Syöte 3

6
5 1 4 4 2 3

Tuloste 3

1

Huomautus

Ensimmäisessä testissä Kostekin kannattaa asettaa raja kahden ensimmäisen tornin väliin. Tällöin hänellä on torni, jonka korkeus on $200$, kun taas sinulla on tornit, joiden korkeudet ovat $333$ ja $100$. Korkeimmat torninne ovat $200$ ja $333$, joten tulos on $133$. Pienempää erotusta ei ole mahdollista saavuttaa.

Toisessa testissä mikä tahansa jako tuottaa erotukseksi $0$.

Kolmannessa testissä Kostekin kannattaa asettaa raja ensimmäisen, toisen tai kolmannen tornin jälkeen. Vaadittu erotus on tällöin $|5 - 4| = 1$. Alla oleva kuva näyttää yhden näistä optimaalisista vaihtoehdoista: