D. 比赛

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

2^N 个玩家进行比赛,将在单淘汰赛程序比赛中相互竞争。

每个人有一个等级系数 Ai ,任何两个玩家都有不同的评级,两个玩家之间的比赛总是以评级更高的玩家获胜。

比赛如下进行:

对于每个 i=1,2,3,…,N 的整数,按照这个顺序,会发生以下情况

对于每一个整数 j ( 1≤j≤2^{N−i} ),在未输过的玩家中,第 ( 2j−1 ) 个的玩家和第 2j 个的玩家进行一场比赛。

找到获得第二名(即在最后一场比赛中输球的选手)的序号。

输入格式

第一行,N

第二行, 2^N 个玩家的等级系数

输出格式

第二名选手的标签

样例

输入样例1

2
1 4 2 5

输出样例1

2

解释:第2个选手(等级为4)获得第二名

输入样例2

2
3 1 5 4

输出样例2

1

解释:第1个选手(等级为3)获得第二名

输入样例3

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

输出样例3

2

解释:第2个选手(等级为13)获得第二名

数据范围与提示

1<= N <= 16

1 <= Ai <= 10^9

所有的 Ai 互不相同

所有的输入都是整数