CF1260E.Tournament

You are organizing a boxing tournament, where $n$ boxers will participate ($n$ is a power of $2$), and your friend is one of them. All boxers have different strength from $1$ to $n$, and boxer $i$ wins in the match against boxer $j$ if and only if $i$ is stronger than $j$.

The tournament will be organized as follows: $n$ boxers will be divided into pairs; the loser in each pair leaves the tournament, and $\frac{n}{2}$ winners advance to the next stage, where they are divided into pairs again, and the winners in all pairs advance to the next stage, and so on, until only one boxer remains (who is declared the winner).

Your friend really wants to win the tournament, but he may be not the strongest boxer. To help your friend win the tournament, you may bribe his opponents: if your friend is fighting with a boxer you have bribed, your friend wins even if his strength is lower.

Furthermore, during each stage you distribute the boxers into pairs as you wish.

The boxer with strength $i$ can be bribed if you pay him $a_i$ dollars. What is the minimum number of dollars you have to spend to make your friend win the tournament, provided that you arrange the boxers into pairs during each stage as you wish?

你正在组织一场拳击锦标赛，共有 $n$ 名拳手参赛（$n$ 是 $2$ 的幂），而你的朋友是其中一员。所有拳手的实力互不相同，取值范围为 $1$ 到 $n$；拳手 $i$ 在与拳手 $j$ 的对决中获胜当且仅当 $i$ 的实力强于 $j$。

锦标赛的赛制如下：$n$ 名拳手首先被分成 $\frac{n}{2}$ 对；每对中实力较弱者被淘汰，实力较强者晋级下一轮；下一轮中剩余的 $\frac{n}{2}$ 名拳手再次被任意配对，每对中的胜者继续晋级；如此反复，直至仅剩一名拳手（即最终冠军）。

你的朋友非常渴望赢得整个锦标赛，但他未必是实力最强的拳手。为了帮助他夺冠，你可以贿赂他的对手：若你的朋友在某场比赛中对阵一名已被你贿赂的拳手，则无论其实力高低，你的朋友都将获胜。

此外，在每一阶段，你都可以自由安排所有参赛拳手的配对方式。

贿赂实力为 $i$ 的拳手需花费 $a_i$ 美元。在你可以自由安排每轮配对的前提下，使你的朋友最终夺冠所需的最小花费是多少美元？

The first line contains one integer $n$ ($2 \le n \le 2^{18}$) — the number of boxers. $n$ is a power of $2$.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$, where $a_i$ is the number of dollars you have to pay if you want to bribe the boxer with strength $i$. Exactly one of $a_i$ is equal to $-1$ — it means that the boxer with strength $i$ is your friend. All other values are in the range $[1, 10^9]$.

第一行包含一个整数 $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]$ 内。

Print one integer — the minimum number of dollars you have to pay so your friend wins.

输出一个整数——你至少需要支付的美元数量，以确保你的朋友获胜。

In the first test case no matter how you will distribute boxers into pairs, your friend is the strongest boxer and anyway wins the tournament.

In the second test case you can distribute boxers as follows (your friend is number $2$):

$1 : 2, 8 : 5, 7 : 3, 6 : 4$ (boxers $2, 8, 7$ and $6$ advance to the next stage);

$2 : 6, 8 : 7$ (boxers $2$ and $8$ advance to the next stage, you have to bribe the boxer with strength $6$);

$2 : 8$ (you have to bribe the boxer with strength $8$);

在第一个测试用例中，无论你如何将拳击手配对，你的朋友都是最强的拳击手，因此无论如何都会赢得锦标赛。

在第二个测试用例中，你可以如下分配拳击手（你的朋友编号为 $2$）：

$1 : 2, 8 : 5, 7 : 3, 6 : 4$（拳击手 $2, 8, 7$ 和 $6$ 进入下一轮）；

$2 : 6, 8 : 7$（拳击手 $2$ 和 $8$ 进入下一轮，你必须贿赂力量值为 $6$ 的拳击手）；

$2 : 8$（你必须贿赂力量值为 $8$ 的拳击手）；