Разом із маленьким Костеком ви будуєте вежі з кубиків. Ви вже побудували $n$ веж у ряд, причому висота $i$-ї вежі дорівнює $h_i$. Тепер Костек хоче провести межу між своїми та вашими вежами. Вежі ліворуч від межі належатимуть Костеку, а решта веж праворуч будуть вашими. У кожного з вас має бути принаймні одна вежа.

Ви збираєтеся перейти до наступної гри, яка починається з того, що кожен із вас ставить розвідника на свою найвищу вежу. Гра буде нецікавою, якщо розвідники стоятимуть на зовсім різній висоті. Тому вам слід запропонувати якомога справедливіший поділ — обрати межу так, щоб мінімізувати абсолютне значення різниці між висотою найвищої вежі Костека та вашої. Виведіть цю мінімальну різницю.

Вхідні дані

Перший рядок містить ціле число $n$ ($2 \le n \le 300\,000$), що позначає кількість веж.

Другий рядок містить $n$ цілих чисел $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), що позначають висоти послідовних веж зліва направо.

Вихідні дані

Виведіть одне ціле число — найменшу можливу різницю у висоті між найвищою з ваших веж і найвищою з веж Костека.

Приклади

Вхідні дані 1

3
200 333 100

Вихідні дані 1

133

Вхідні дані 2

5
5 2 4 1 5

Вихідні дані 2

0

Вхідні дані 3

6
5 1 4 4 2 3

Вихідні дані 3

1

Примітка

У першому тесті Костеку слід провести межу між першими двома вежами. Тоді він матиме вежу висоти $200$, а ви — вежі висоти $333$ і $100$. Ваші найвищі вежі мають висоти $200$ і $333$, тому результат дорівнює $133$. Меншу різницю отримати неможливо.

У другому тесті будь-який поділ дає різницю $0$.

У третьому тесті Костеку слід провести межу після першої, другої або третьої вежі. Тоді шукана різниця дорівнює $|5 - 4| = 1$. На рисунку нижче показано один із таких оптимальних варіантів: