← 返回题目列表

AtCoder · abc188_c

C. ABC 锦标赛

中文机器翻译题面 查看原题

分数: 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