Insieme al piccolo Kostek, stai costruendo delle torri con i mattoncini. Avete già costruito $n$ torri in fila, la $i$-esima di altezza $h_i$. Ora Kostek vuole fissare un confine tra le sue torri e le tue. Le torri a sinistra del confine apparterranno a Kostek, mentre le restanti torri a destra saranno tue. Ciascuno di voi deve avere almeno una torre.

State per passare al gioco successivo, che inizia con ciascuno di voi che posiziona una vedetta sulla propria torre più alta. Il gioco non sarà divertente se le vedette si trovano ad altezze completamente diverse. Pertanto, dovresti suggerire la divisione più equa possibile: scegli il confine in modo da minimizzare il valore assoluto della differenza tra l'altezza della torre più alta di Kostek e la tua. Stampa questa differenza minima.

Input

La prima riga contiene un intero $n$ ($2 \le n \le 300\,000$), che indica il numero di torri.

La seconda riga contiene $n$ interi $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), che indicano le altezze delle torri consecutive da sinistra a destra.

Output

Stampa un intero – la minima differenza di altezza possibile tra la più alta delle tue torri e la più alta delle torri di Kostek.

Esempi

Input 1

3
200 333 100

Output 1

133

Input 2

5
5 2 4 1 5

Output 2

0

Input 3

6
5 1 4 4 2 3

Output 3

1

Note

Nel primo test, Kostek dovrebbe fissare il confine tra le prime due torri. Egli ha quindi una torre di altezza $200$, mentre tu hai torri di altezze $333$ e $100$. Le vostre torri più alte sono $200$ e $333$, quindi il risultato è $133$. Non è possibile ottenere una differenza minore.

Nel secondo test, qualsiasi divisione porta a una differenza pari a $0$.

Nel terzo test, Kostek dovrebbe fissare il confine dopo la prima, la seconda o la terza torre. La differenza richiesta è quindi $|5 - 4| = 1$. Il diagramma sottostante mostra una di queste possibilità ottimali: