Gemeinsam mit dem kleinen Kostek bauen Sie Türme aus Bauklötzen. Sie haben bereits $n$ Türme in einer Reihe gebaut, wobei der $i$-te Turm die Höhe $h_i$ hat. Nun möchte Kostek eine Grenze zwischen seinen und Ihren Türmen ziehen. Die Türme links von der Grenze gehören Kostek, und die übrigen Türme rechts davon gehören Ihnen. Jeder von Ihnen muss mindestens einen Turm erhalten.

Sie wollen gleich zum nächsten Spiel übergehen, das damit beginnt, dass jeder von Ihnen einen Späher auf seinen höchsten Turm stellt. Das Spiel macht keinen Spaß, wenn die Späher auf völlig unterschiedlichen Höhen stehen. Daher sollten Sie die gerechteste Aufteilung vorschlagen – wählen Sie die Grenze so, dass der Absolutbetrag der Differenz zwischen der Höhe von Kosteks höchstem Turm und Ihrem höchsten Turm minimiert wird. Geben Sie diese minimale Differenz aus.

Eingabe

Die erste Zeile enthält eine ganze Zahl $n$ ($2 \le n \le 300\,000$), die die Anzahl der Türme angibt.

Die zweite Zeile enthält $n$ ganze Zahlen $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), die die Höhen der aufeinanderfolgenden Türme von links nach rechts angeben.

Ausgabe

Geben Sie eine ganze Zahl aus – den kleinstmöglichen Höhenunterschied zwischen dem höchsten Ihrer Türme und dem höchsten von Kosteks Türmen.

Beispiele

Eingabe 1

3
200 333 100

Ausgabe 1

133

Eingabe 2

5
5 2 4 1 5

Ausgabe 2

0

Eingabe 3

6
5 1 4 4 2 3

Ausgabe 3

1

Hinweis

Im ersten Test sollte Kostek die Grenze zwischen den ersten beiden Türmen ziehen. Er hat dann einen Turm der Höhe $200$, während Sie Türme der Höhen $333$ und $100$ haben. Ihre höchsten Türme sind $200$ und $333$, sodass das Ergebnis $133$ lautet. Eine kleinere Differenz ist nicht erreichbar.

Im zweiten Test führt jede Aufteilung zu einer Differenz von $0$.

Im dritten Test sollte Kostek die Grenze nach dem ersten, zweiten oder dritten Turm ziehen. Die gesuchte Differenz beträgt dann $|5 - 4| = 1$. Das folgende Diagramm zeigt eine dieser optimalen Möglichkeiten: