Во Скопје ќе се одржува шаховски турнир. Ќе има точно N ( N е секогаш 2^M ) играчи. Секој играч има рејтинг - природен број.

Тие се подредени во ред, како што е прикажано на сликата, и секоја игра од прво ниво се игра помеѓу двајца играчи (првиот со вториот, третиот со четвртиот...). Во дадена игра секогаш губи играчот со помал рејтинг, а победникот продолжува во следното ниво. Во случај на натпревар меѓу играчи со ист рејтинг случајно се избира победник, т.е. нема нерешени игри.

Организаторот на турнирот му плаќа на победникот на секоја игра одредена сума. Притоа, колку е поголема разликата во рејтинг меѓу двата играчи, толку е помала исплатата, бидејќи се смета дека победникот полесно победил. Таа разлика (поголемиот минус помалиот рејтинг) ќе ја нарекуваме гап на играта.

Организаторот констатирал дека ќе исплати најмалку пари за целиот турнир ако сумата од гаповите од сите одиграни игри е најголемата можна.

Организаторот има можност самиот да го направи иницијалниот распоред на игрите. Помогнете му со наоѓање на распоредот кој ќе обезбеди најголема сума од гаповите од сите одиграни игри.

За примерот на сликата, сумата изнесува 5000 ако распоредот е како на сликата. За дадениот пример би добиле поголема сума, доколку во распоредот даден на влез си ги променат местата играчите со рејтинг 800 и 2000, при што новата сума ќе изнесува 5800. Објаснувања за пресметувањето на сумата се дадени најдолу.

Влез

Во првиот ред ви е даден еден цел број N ( 4 ≤ N ≤ 2¹⁹ ) – бројот на играчи, каде N е секогаш степен на два.
Во вториот ред ви се дадени N цели броеви R_i ( 1 ≤ R_i ≤ 10⁹ ) – рејтингот на играчите. Броевите ви се дадени во не-растечки редослед, бидејќи играчите со најголем рејтинг први се појавуваат на турнирот.

Излез

Во еден ред отпечатете ја максималната сума на гапови при оптимален иницијален распоред на игрите.

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

Временско ограничување: 300 milliseconds
Мемориско ограничување: 1 megabyte

Внимавајте: Оваа задача има специфичен (многу мал) мемориски лимит (видете погоре). Вашата програма не може да користи повеќе меморија од дозволеното - имено, тоа може да резултира со грешка при извршување (runtime error, излезен код различен од 0).

Примери

влез
8
2800 2500 2000 1800 1600 1500 1200 800

излез
5800

Објаснување за пресметките за подредувањето на сликата:

1200 800 1500 2500 2000 2800 1600 1800

Игра 1: 1200 против 800, победник 1200, гап 400
Игра 2: 1500 против 2500, победник 2500, гап 1000
Игра 3: 2000 против 2800, победник 2800, гап 800
Игра 4: 1600 против 1800, победник 1800, гап 200
Игра 5: 1200 против 2500, победник 2500, гап 1300
Игра 6: 2800 против 1800, победник 2800, гап 1000
Игра 7: 2500 против 2800, победник 2800, гап 300

Сума на сите гапови: 5000

Објаснување за пресметките при променето место на играчите со рејтинг 800 и 2000

Игра 1: 1200 против 2000, победник 2000, гап 800
Игра 2: 1500 против 2500, победник 2500, гап 1000
Игра 3: 800 против 2800, победник 2800, гап 2000
Игра 4: 1600 против 1800, победник 1800, гап 200
Игра 5: 2000 против 2500, победник 2500, гап 500
Игра 6: 2800 против 1800, победник 2800, гап 1000
Игра 7: 2500 против 2800, победник 2800, гап 300

Сума на сите гапови: 5800