CF1260E Tournament

你正在组织一场拳击锦标赛，共有 $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, \dots, a_n$，其中 $a_i$ 表示贿赂实力为 $i$ 的拳击手所需的美元数。恰好有一个 $a_i$ 等于 $-1$——表示实力为 $i$ 的拳击手是你的朋友。其余所有值均在 $[1, 10^9]$ 范围内。

输出一个整数——为了让你的朋友获胜，你需要支付的最小美元数。

在第一个测试用例中，无论你如何分配拳击手的配对，你的朋友都是最强的拳击手，无论如何都会获胜。 在第二个测试用例中，你可以按如下方式分配拳击手（你的朋友是 $2$ 号）： $1 : 2, 8 : 5, 7 : 3, 6 : 4$（拳击手 $2, 8, 7$ 和 $6$ 晋级到下一轮）； $2 : 6, 8 : 7$（拳击手 $2$ 和 $8$ 晋级到下一轮，你需要贿赂实力为 $6$ 的拳击手）； $2 : 8$（你需要贿赂实力为 $8$ 的拳击手）。 翻译由 DeepSeek V3 完成