您正在组织一场拳击锦标赛,$$$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]$$$ 范围内。
输出
打印一个整数 — 为了让你的朋友获胜,你必须支付的最低金额。
示例
输入 #1
4 3 9 1 -1
输出 #1
0
输入 #2
8 11 -1 13 19 24 7 17 5
输出 #2
12
注意
在第一个测试用例中,无论您如何将拳击手配对,您的朋友都是最强的拳击手,并且无论如何都会赢得比赛。
在第二个测试用例中,您可以按如下方式分配拳击手(您的朋友编号为 $$$2$$$):
$$$1 : 2, 8 : 5, 7 : 3, 6 : 4$$$(拳击手$$$2, 8, 7$$$ 和 $$$6$$$ 晋级下一阶段);
$$$2 : 6, 8 : 7$$$(拳击手$$$2$$$和$$$8$$$晋级下一阶段,你必须用力量贿赂拳击手$$$6$$$);
$$$2 : 8$$$ (你必须用力量贿赂拳击手$$$8$$$);