Разом із маленьким Костеком ви будуєте вежі з кубиків. Ви вже побудували $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$. На рисунку нижче показано один із таких оптимальних варіантів:
