Sammen med lille Kostek bygger du tårn av klosser. Dere har allerede bygget $n$ tårn på rad, der det $i$-te tårnet har høyden $h_i$. Nå vil Kostek sette en grense mellom sine og dine tårn. Tårnene til venstre for grensen vil tilhøre Kostek, og de resterende tårnene til høyre blir dine. Hver av dere må ha minst ett tårn.
Dere skal akkurat til å gå videre til neste lek, som begynner med at hver av dere plasserer en speider på sitt høyeste tårn. Leken blir ikke morsom hvis speiderne står på helt forskjellige høyder. Derfor bør du foreslå en så rettferdig fordeling som mulig – velg grensen slik at absoluttverdien av differansen mellom høyden på Kosteks høyeste tårn og ditt høyeste tårn minimeres. Skriv ut denne minimale differansen.
Inndata
Den første linjen inneholder et heltall $n$ ($2 \le n \le 300\,000$), som angir antallet tårn.
Den andre linjen inneholder $n$ heltall $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), som angir høydene på de påfølgende tårnene fra venstre mot høyre.
Utdata
Skriv ut ett heltall – den minste mulige høydeforskjellen mellom det høyeste av dine tårn og det høyeste av Kosteks tårn.
Eksempler
Inndata 1
3 200 333 100
Utdata 1
133
Inndata 2
5 5 2 4 1 5
Utdata 2
0
Inndata 3
6 5 1 4 4 2 3
Utdata 3
1
Forklaring
I den første testen bør Kostek sette grensen mellom de to første tårnene. Han har da et tårn med høyde $200$, mens du har tårn med høydene $333$ og $100$. Deres høyeste tårn er $200$ og $333$, så resultatet er $133$. Det er ikke mulig å oppnå en mindre forskjell.
I den andre testen gir enhver oppdeling en forskjell på $0$.
I den tredje testen bør Kostek sette grensen etter det første, andre eller tredje tårnet. Den ønskede forskjellen er da $|5 - 4| = 1$. Diagrammet nedenfor viser én av disse optimale mulighetene:
