Ásamt Kostek litla ertu að byggja turna úr kubbum. Þið hafið þegar byggt $n$ turna í röð, þar sem $i$-ti turninn hefur hæðina $h_i$. Nú vill Kostek setja mörk á milli turnanna sinna og þinna. Turnarnir vinstra megin við mörkin munu tilheyra Kostek og turnarnir sem eftir eru hægra megin verða þínir. Hvorugt ykkar má vera án turns, svo bæði verðið þið að eiga að minnsta kosti einn turn.

Þið eruð í þann mund að færa ykkur yfir í næsta leik, sem hefst á því að hvort ykkar setur njósnara á hæsta turninn sinn. Leikurinn verður ekki skemmtilegur ef njósnararnir standa í gjörólíkri hæð. Því ættir þú að leggja til eins sanngjarna skiptingu og mögulegt er – veldu mörkin þannig að tölugildi mismunarins á hæð hæsta turns Kosteks og hæsta turns þíns verði sem minnst. Prentaðu þennan lágmarksmismun.

Inntak

Fyrsta línan inniheldur heiltölu $n$ ($2 \le n \le 300\,000$), sem táknar fjölda turna.

Önnur línan inniheldur $n$ heiltölur $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), sem tákna hæðir samliggjandi turna frá vinstri til hægri.

Úttak

Prentaðu eina heiltölu – minnsta mögulega hæðarmun á hæsta turninum þínum og hæsta turni Kosteks.

Dæmi

Inntak 1

3
200 333 100

Úttak 1

133

Inntak 2

5
5 2 4 1 5

Úttak 2

0

Inntak 3

6
5 1 4 4 2 3

Úttak 3

1

Athugasemd

Í fyrsta prófunartilvikinu ætti Kostek að setja mörkin á milli fyrstu tveggja turnanna. Hann er þá með turn af hæð $200$, á meðan þú ert með turna af hæðunum $333$ og $100$. Hæstu turnarnir ykkar eru $200$ og $333$, svo niðurstaðan er $133$. Það er ekki hægt að ná minni mismun.

Í öðru prófunartilvikinu gefur hvaða skipting sem er mismuninn $0$.

Í þriðja prófunartilvikinu ætti Kostek að setja mörkin á eftir fyrsta, öðrum eða þriðja turninum. Umbeðinn mismunur er þá $|5 - 4| = 1$. Myndin hér að neðan sýnir einn af þessum bestu möguleikum: