За да може успешно да се организира еден натпревар по информатика, потребно е да се направи распоред на седење на учесниците на натпреварот. Весна, која е одговорна за распоредот на седење на натпреварувачите на Државниот натпревар по информатика, го знае следното:

1. Лабораторијата со компјутери има правоаголна форма со клупи наместени до сите ѕидови; и компјутери поставени на нив. Така, сите натпреварувачи седнуваат на некоја од клупите свртени кон ѕидовите на училницата.
2. Според горниот опис, секој натпреварувач има по точно два соседни натпреварувачи (лево и десно од него). Бидејќи постои мааала можност даден натпреварувач да ѕирка во мониторите на натпреварувачот од лево и натпреварувачот од десно, при правењето на распоредот треба да се внимава разликата во знаењата на два натпреварувачи кои седат еден до друг да е најмала можна.

Значи, Весна треба да направи распоред за седење така што ќе се минимизира најголемата разлика во знаење помеѓу кои било натпреварувачи што седат еден до друг. Со други зборови, не треба да постои друг распоред на седење во кој сите парови натпреварувачи кои седат еден до друг имаат помала разлика во знаење од парот со максимална разлика во нашиот (оптимален) распоред.

На пример, нека треба да се распоредат петмина натпреварувачи, и нека нивното знаење изнесува 11, 14, 14, 9 и 16. Тогаш, можно е тие да се распоредат во една училница на неколку начини. Два од нив се прикажани на следната слика.

На првиот распоред (лево на сликата), постојат два натпреварувачи кои седат еден до друг, а нивната разлика во знаење изнесува 16-9=7. На вториот распоред (десно на сликата), најголемата разлика помеѓу кои било два натпреварувачи кои седат еден до друг е 5. Како и да ги редиме натпреварувачите, не постои распоред на седење со помала ваква разлика.

Влез

Во првата линија е запишан еден цел број N (3 ≤ N ≤ 18), кој го означува бројот на натпреварувачи.

Во втората линија се запишани N цели броеви Zi (1 ≤ Zi ≤ 10000), кои го означуваат знаењето на секој натпреварувач.

Забелешка: Во тест случаи кои вредат најмалку 30% од поените, ќе важи 3 ≤ N ≤ 10.

Излез

Да се отпечати максималната разлика во знаење помеѓу кои било два натпреварувачи кои седат еден до друг, при оптимален распоред на седење на учесниците на натпреварот.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5
11 14 14 9 16

излез
5

влез
3
10 20 30

излез
20

влез
7
13 15 19 11 19 27 23

излез
8