Codeforces-1260-E. 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 n2 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 ai 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?

Input

The first line contains one integer n (2≤n≤218) — the number of boxers. n is a power of 2.

The second line contains n integers a1, a2, …, an, where ai is the number of dollars you have to pay if you want to bribe the boxer with strength i. Exactly one of ai is equal to −1 — it means that the boxer with strength i is your friend. All other values are in the range [1,109].

Output

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

Examples

Input

4
3 9 1 -1

Output

0

Input

8
11 -1 13 19 24 7 17 5

Output

12

Note

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);

题意：

有n个人，第i个人有力量值i，这n个人中，每次对局两两之间进行solo，如果说一个人的力量之大于他的对手，这个人是赢的，赢得比赛的选手会进入下一轮比赛中。

然而里面有一个人为你的朋友，他或许并不是里面最强的人，要想让朋友成为冠军，就需要对必要的人进行贿赂，求出最少需要花费多少才能使得朋友成为冠军。在每次对局中，都可以进行任意的对局安排，对局安排只取决于自己

题解：

首先放上qsc学长的B站链接

首先有几个性质：

① 如果说朋友在进行比赛的时候干掉了三个人：

a[p1] a[p2] a[p3] ，那么从贪心的角度来讲，当p1 < p2 < p3的时候，这种情况才是最优的

因为第一个人a[p1] 相比较于a[p2]来讲，更容易死，换句话说就是第二个人更容易活下来，在接下来的对局中就有可能再次被选

② 如果说朋友不是最强的，那么必然要贿赂最后一个人a[n]

因为只要有最后一个人存在，这个人就会阻止朋友成为冠军

③ 在第k轮中，前面的2k - 1个人是不能够选择的，只能够选择后面的半部分，并且在每次中，只能够选择区间内的最小值来办证贪心的最优

（比如在第一次对局中，我可以安排朋友选择任意一个人来进行对局，但是在第二次对局中，我就不能够再次选择1号人物，因为这个人并不能够活到第二次对局，在第一次对局就已经被ko了，不是被自己ko就是被比1强的其他人ko）

Code:

要注意只在二的幂次的时候进行选择

ll a[maxn];
multiset<ll> s;
int main() {
    int n; cin >>n;
    for(int i=1;i<=n;i++) {
        a[i] = read;
    }
    ll sum = 0;
    for(int i = n;i >= 1;i --){
        if(a[i] == -1) break;
        s.insert(a[i]);
        if((i & (i - 1)) == 0){
            sum += *s.begin();
            s.erase(s.begin());
        }
    }
    cout << sum << endl;
    return 0;
}