E. Турнир
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы организуете боксерский турнир, в котором участвует $$$n$$$ боксеров ($$$n$$$ это степень $$$2$$$), и один из боксеров ваш друг. Все боксеры имеют различную силу от $$$1$$$ до $$$n$$$, и боксер $$$i$$$ побеждает боксера $$$j$$$, когда $$$i$$$ больше чем $$$j$$$.

Турнир орагнизовывается следующим образом: $$$n$$$ боксеров делятся на пары; проигравший в каждой паре выбывает из турнира, а $$$\frac{n}{2}$$$ победителей проходят в следующий этап, в котором снова делятся на пары, после чего победители опять проходят в следующий этап, и так далее, пока не останется только один боксер (он считается победителем).

Ваш друг сильно хочет выиграть это турнир, но возможно, он не самый сильный боксер. Для того, чтобы помочь другу выиграть турнир, вы можете подкупать его противников: если ваш друг будет драться с боксером, которого вы подкупили, то ваш друг выиграет, даже если он слабее.

На каждом этапе вы сами делите боксеров на пары.

Боксера с силой $$$i$$$ можно подкупить, заплатив ему $$$a_i$$$ долларов. Какое минимальное количество долларов вам нужно потратить для того, чтобы ваш друг победил, если на каждом этапе вы сами делите всех боксеров на пары?

Входные данные

Первая строка содержит число $$$n$$$ ($$$2 \le n \le 2^{18}$$$) — количество боксеров. $$$n$$$ обязательно равна степени $$$2$$$.

Вторая строка содержит $$$n$$$ чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$, где $$$a_i$$$ равно количеству долларов, которое вам нужно заплатить для подкупа боксера с силой $$$i$$$. Ровно одно число $$$a_i$$$ равно $$$-1$$$ — это значит, что боксер с силой $$$i$$$ ваш друг. Все остальные числа находятся в отрезке $$$[1, 10^9]$$$.

Выходные данные

Выведите одно число — минимальное количество долларов, которое вам нужно потратить для победы вашего друга.

Примеры
Входные данные
4
3 9 1 -1
Выходные данные
0
Входные данные
8
11 -1 13 19 24 7 17 5
Выходные данные
12
Примечание

В первом тестовом примере не важно как вы будете распределять боксеров, так как ваш друг самый сильный из них и выиграет в любом случае.

Во втором тестовом примере вы можете распределять боксеров в пары следующим образом (под номером $$$2$$$ ваш друг):

$$$1 : 2, 8 : 5, 7 : 3, 6 : 4$$$ (боксеры $$$2, 8, 7$$$ и $$$6$$$ проходят в следующий этап);

$$$2 : 6, 8 : 7$$$ (боксеры $$$2$$$ и $$$8$$$ проходят в следующий этап, вам нужно подкупить боксера с силой $$$6$$$);

$$$2 : 8$$$ (вам нужно подкупить боксера с силой $$$8$$$);