A - ロボットバトル大会 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 266 点

問題文

高橋君は N 台のロボットが参加するバトル大会を開催します。ロボットには 1 から N までの番号が付けられています。なお、N は 2 の累乗です。

高橋君は各ロボットの戦闘力を把握しています。ロボット i の戦闘力は A_i です。すべてのロボットの戦闘力は異なり、2台のロボットが対戦したとき、戦闘力が高い方が必ず勝ちます。

この大会はトーナメント戦で行われます。トーナメントの進行は以下の通りです。

  • 最初に、ロボットを番号 1, 2, 3, \ldots, N の順に一列に並べます。
  • 列に残っているロボットが2台以上である間、以下の操作を繰り返します。この操作1回分をラウンドと呼びます。
  • 現在の列の先頭から順に2台ずつ組にして対戦させます。すなわち、現在の列の 1 番目と 2 番目、3 番目と 4 番目、5 番目と 6 番目、…がそれぞれ対戦します。
  • 各対戦の勝者を、組の順序を保ったまま（先頭側の組の勝者から順に）並べて新たな列とします。これにより、列のロボットの台数はちょうど半分になります。
  • 列にロボットが1台だけ残ったとき、そのロボットが優勝です。

N は 2 の累乗であるため、各ラウンドの開始時点で列のロボット数は必ず偶数となり、すべてのロボットが余りなく組になります。

このトーナメントで優勝するロボットの番号を求めてください。

制約

  • N は 2 の累乗である
  • 2 \leq N \leq 2^{20}
  • 1 \leq A_i \leq 10^9
  • A_i \neq A_j （i \neq j）
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、参加ロボットの台数を表す整数 N が与えられる。
  • 2 行目には、各ロボットの戦闘力を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

トーナメントで優勝するロボットの番号を 1 行で出力してください。

入力例 1

4
3 1 4 2

出力例 1

3

入力例 2

8
5 3 8 1 6 2 7 4

出力例 2

3

入力例 3

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

出力例 3

7

Score : 266 pts

Problem Statement

Takahashi is hosting a battle tournament with N robots participating. The robots are numbered from 1 to N. Note that N is a power of 2.

Takahashi knows the combat power of each robot. The combat power of robot i is A_i. All robots have distinct combat powers, and when two robots battle each other, the one with higher combat power always wins.

This tournament is conducted in a knockout format. The tournament proceeds as follows:

  • First, the robots are arranged in a line in the order of their numbers 1, 2, 3, \ldots, N.
  • While there are 2 or more robots remaining in the line, the following operation is repeated. One execution of this operation is called a round.
  • Starting from the beginning of the current line, robots are paired up in groups of 2 and made to battle. That is, the 1st and 2nd, 3rd and 4th, 5th and 6th, … of the current line battle each other respectively.
  • The winners of each match are arranged in a new line, preserving the order of the pairs (in order from the winner of the pair closest to the front). This causes the number of robots in the line to become exactly half.
  • When only 1 robot remains in the line, that robot is the champion.

Since N is a power of 2, the number of robots in the line at the start of each round is always even, and all robots are paired without any remainder.

Find the number of the robot that wins this tournament.

Constraints

  • N is a power of 2
  • 2 \leq N \leq 2^{20}
  • 1 \leq A_i \leq 10^9
  • A_i \neq A_j (i \neq j)
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N, representing the number of participating robots.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the combat power of each robot.

Output

Print the number of the robot that wins the tournament on a single line.

Sample Input 1

4
3 1 4 2

Sample Output 1

3

Sample Input 2

8
5 3 8 1 6 2 7 4

Sample Output 2

3

Sample Input 3

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

Sample Output 3

7