ABC 锦标赛

题目描述

编号为选手 $1$ 到选手 $2^N$ 的 $2^N$ 名选手将进行锦标赛形式的编程对决。

选手 $i$ 的评分（rate）为 $A_i$。任意两名选手的评分都不同，两名选手对战时，评分较高者总是获胜。

锦标赛对阵表是满二叉树的形状。

更准确地说，本次锦标赛按以下方式进行：

• 依次对 $i = 1, 2, 3, \dots, N$ 进行如下操作：
  • 对每个整数 $j (1 \le j \le 2^{N - i})$，在尚未输过的选手中，编号第 $2j - 1$ 小的选手与编号第 $2j$ 小的选手对战。

求获得亚军（即在最后一场对战中输掉的选手）的选手编号。

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $A_2$ $A_3$ $\dots$ $A_{2^N}$

输出格式

输出获得亚军的选手编号。

样例

2
1 4 2 5

2

首先选手 $1$ 与 $2$、选手 $3$ 与 $4$ 分别对战，根据评分高低，选手 $2$ 和 $4$ 获胜。

接下来选手 $2$ 与选手 $4$ 对战，选手 $4$ 获胜，锦标赛结束。

最后一场对战中输掉的是选手 $2$，因此输出 $2$。

2
3 1 5 4

1

首先选手 $1$ 与 $2$、选手 $3$ 与 $4$ 分别对战，根据评分高低，选手 $1$ 和 $3$ 获胜。

接下来选手 $1$ 与选手 $3$ 对战，选手 $3$ 获胜，锦标赛结束。

最后一场对战中输掉的是选手 $1$，因此输出 $1$。

4
6 13 12 5 3 7 10 11 16 9 8 15 2 1 14 4

2

数据范围

• $1 \le N \le 16$
• $1 \le A_i \le 10^9$
• $A_i$ 互不相同
• 输入中包含的值均为整数