ABC Tournament

题目描述

$2^N$ 名选手，编号为 $1$ 到 $2^N$，将在一个单败淘汰编程比赛中相互对决。
选手 $i$ 的评分为 $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

2
3 1 5 4

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$ 两两不同。 输入中的所有数值均为整数。首先，先进行两场比赛，分别为选手 $1$ 与 $2$，以及选手 $3$ 与 $4$。根据评分，选手 $2$ 与 $4$ 将获胜。
然后，选手 $2$ 与 $4$ 进行一场比赛，比赛以选手 $4$ 成为冠军结束。
在决赛中失利的选手是选手 $2$，所以我们应输出 $2$.
首先，先进行两场比赛，分别为选手 $1$ 与 $2$，以及选手 $3$ 与 $4$。根据评分，选手 $1$ 与 $3$ 将获胜。
然后，选手 $1$ 与 $3$ 进行一场比赛，比赛以选手 $3$ 成为冠军结束。
在决赛中失利的选手是选手 $1$，所以我们应输出 $1$.

标签: AtCoder|abc188C

来源

AtCoder|abc188C