Кішкентай Костекпен бірге сіз текшелерден мұнаралар тұрғызып жатырсыз. Сіздер бір қатарға $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$ болады. Төмендегі суретте осы тиімді мүмкіндіктердің бірі көрсетілген:
