分数: 300 点
问题陈述
2^N 玩家,标记为 1 通过 2^N,将在单淘汰编程锦标赛中相互竞争。
玩家的评分 i is A_i。任何两名玩家都有不同的评分,两名玩家之间的比赛总是导致评分较高的玩家获胜。
锦标赛看起来像一个完美的二叉树。
比赛将正式进行如下:
- 对于每个整数 i = 1, 2, 3, \dots, N 按照这个顺序,会发生以下情况。
- 对于每个整数 j (1 \le j \le 2^{N - i}),在从未输过的玩家中,拥有 (2j - 1)-第一个最小的标签和具有 2j-最小的标签互相进行比赛。
找到将采取的玩家的标签 第二名,即最后一场比赛输了。
约束
- 1 \le N \le 16
- 1 \le A_i \le 10^9
- A_i 两两不同。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 A_3 \dots A_{2^N}
输出
打印将采取的玩家的标签 第二名.
示例输入 1
2 1 4 2 5
示例输出 1
2
首先,玩家之间将进行两场比赛 1 和 2 以及玩家之间 3 和 4。根据玩家的评分 2 和 4 将会获胜。
然后,玩家之间将进行一场比赛 2 和 4,锦标赛将以 Player 结束 4 成为冠军。
最终比赛中失败的玩家是玩家 2,所以我们应该打印 2.
示例输入 2
2 3 1 5 4
示例输出 2
1
首先,玩家之间将进行两场比赛 1 和 2 以及玩家之间 3 和 4。根据玩家的评分 1 和 3 将会获胜。
然后,玩家之间将进行一场比赛 1 和 3,锦标赛将以 Player 结束 3 成为冠军。
最终比赛中失败的玩家是玩家 1,所以我们应该打印 1.
示例输入 3
4 6 13 12 5 3 7 10 11 16 9 8 15 2 1 14 4
示例输出 3
2