Tillsammans med lille Kostek bygger du torn av klossar. Ni har redan byggt $n$ torn på rad, där det $i$-te tornet har höjden $h_i$. Nu vill Kostek sätta en gräns mellan sina och dina torn. Tornen till vänster om gränsen kommer att tillhöra Kostek, och de återstående tornen till höger blir dina. Var och en av er måste ha minst ett torn.

Ni ska precis gå vidare till nästa lek, som börjar med att var och en av er placerar en spejare på sitt högsta torn. Leken blir inte rolig om spejarna står på helt olika höjder. Därför bör du föreslå en så rättvis uppdelning som möjligt – välj gränsen så att absolutbeloppet av skillnaden mellan höjden på Kosteks högsta torn och ditt högsta torn minimeras. Skriv ut denna minimala skillnad.

Indata

Den första raden innehåller ett heltal $n$ ($2 \le n \le 300\,000$), som anger antalet torn.

Den andra raden innehåller $n$ heltal $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), som anger höjderna på de på varandra följande tornen från vänster till höger.

Utdata

Skriv ut ett heltal – den minsta möjliga höjdskillnaden mellan det högsta av dina torn och det högsta av Kosteks torn.

Exempel

Indata 1

3
200 333 100

Utdata 1

133

Indata 2

5
5 2 4 1 5

Utdata 2

0

Indata 3

6
5 1 4 4 2 3

Utdata 3

1

Förklaring

I det första testet bör Kostek sätta gränsen mellan de två första tornen. Han har då ett torn med höjden $200$, medan du har torn med höjderna $333$ och $100$. Era högsta torn är $200$ och $333$, så resultatet blir $133$. Det går inte att uppnå en mindre skillnad.

I det andra testet ger varje uppdelning skillnaden $0$.

I det tredje testet bör Kostek sätta gränsen efter det första, andra eller tredje tornet. Den sökta skillnaden blir då $|5 - 4| = 1$. Diagrammet nedan visar en av dessa optimala möjligheter: