/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
選手 1 から選手 2^N までの 2^N 人の選手がトーナメント形式のプログラミング対決をします。
選手 i のレートは A_i です。どの 2 人の選手のレートも異なり、2 人の選手が対戦すると常にレートが高い方が勝ちます。
トーナメント表は完全二分木の形をしています。
より正確には、このトーナメントは以下の要領で行われます。
-
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 が対戦し、選手 4 が勝利してトーナメントが終了します。
最後の対戦で負けるのは選手 2 なので、2 を出力します。
入力例 2
2 3 1 5 4
出力例 2
1
まず選手 1 と 2、選手 3 と 4 がそれぞれ対戦し、レートの大小から選手 1 と 3 が勝利します。
次に選手 1 と選手 3 が対戦し、選手 3 が勝利してトーナメントが終了します。
最後の対戦で負けるのは選手 1 なので、1 を出力します。
入力例 3
4 6 13 12 5 3 7 10 11 16 9 8 15 2 1 14 4
出力例 3
2
Score : 300 points
Problem Statement
2^N players, labeled 1 through 2^N, will compete against each other in a single-elimination programming tournament.
The rating of Player i is A_i. Any two players have different ratings, and a match between two players always results in the victory of the player with the higher rating.
The tournament looks like a perfect binary tree.
Formally, the tournament will proceed as follows:
- For each integer i = 1, 2, 3, \dots, N in this order, the following happens.
- For each integer j (1 \le j \le 2^{N - i}), among the players who have never lost, the player with the (2j - 1)-th smallest label and the player with the 2j-th smallest label play a match against each other.
Find the label of the player who will take second place, that is, lose in the final match.
Constraints
- 1 \le N \le 16
- 1 \le A_i \le 10^9
- A_i are pairwise different.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 A_3 \dots A_{2^N}
Output
Print the label of the player who will take second place.
Sample Input 1
2 1 4 2 5
Sample Output 1
2
First, there will be two matches between Players 1 and 2 and between Players 3 and 4. According to the ratings, Players 2 and 4 will win.
Then, there will be a match between Players 2 and 4, and the tournament will end with Player 4 becoming champion.
The player who will lose in the final match is Player 2, so we should print 2.
Sample Input 2
2 3 1 5 4
Sample Output 2
1
First, there will be two matches between Players 1 and 2 and between Players 3 and 4. According to the ratings, Players 1 and 3 will win.
Then, there will be a match between Players 1 and 3, and the tournament will end with Player 3 becoming champion.
The player who will lose in the final match is Player 1, so we should print 1.
Sample Input 3
4 6 13 12 5 3 7 10 11 16 9 8 15 2 1 14 4
Sample Output 3
2