### IOI '09 - Plovdiv, Bulgaria

## Archery

An archery tournament is held according to the following rules. There are *N* targets arranged in a
line and numbered from 1 to *N* inclusive according to their place on the line (the leftmost target
being target 1, and the rightmost target being target *N*). There are also 2**N* archers. At any time
during the tournament, there are two archers on each target. Every round of the tournament
goes according to the following procedure:

- The two archers on each target compete with each other and determine a winner and a
loser between them. Then all archers are rearranged as follows:
- The winners on targets 2 to
*N*inclusive move to the target on their left (*i.e.*, targets 1 to*N*- 1 respectively). - The losers on targets 2 to
*N*inclusive, as well as the winner on target 1, remain on the same target. - The loser on target 1 moves to target
*N*.

- The winners on targets 2 to

The tournament continues for *R* rounds, with the number of rounds being at least as many as the
number of archers (*i.e.*, *R* ≥ 2**N*).

You are the only archer to arrive for the tournament exactly on time. All other 2**N* - 1 archers
have arrived early and are already standing in a line. What you have to do now is to insert
yourself somewhere into the line amongst them. You know that after you take your position, the
two leftmost archers in the line will start the tournament on target 1, the next two will start on
target 2 and so on, with the two rightmost archers starting on target *N*.

All the 2**N* archers in the tournament (including yourself) are ranked by skill, where a smaller
rank corresponds to better skill. No two archers have the same rank. Also, whenever two archers
compete, the one with the smaller rank will always win.

Knowing how skilled each of your competitors is, you want to insert yourself in such a way as to ensure that you will finish the tournament on a target with as small a number as possible. If there are multiple ways to do this, you prefer the one that starts at a target with as large a number as possible.

Write a program that, given the ranks of all archers, including yourself, as well as your competitors' arrangement on the line, determines on which target you should start the tournament, so that you can achieve your goals as defined above.

### Input

Your program must read from standard input the following data:

- The first line contains the integers
*N*(1 ≤*N*≤ 200 000) and*R*(2**N*≤*R*≤ 1 000 000 000), separated by a space. - The next 2*
*N*lines list the ranks of the archers. The first of these lines contains your rank. The rest of these lines contain the ranks of the other archers, one archer per line, in the order in which they have arranged themselves (from left to right). Each of these 2**N*lines contains a single integer between 1 and 2**N*inclusive. A rank of 1 is the best and a rank of 2**N*is the worst. No two archers have the same rank.

### Output

Your program must write to standard output a single line containing a single integer between 1
and *N* inclusive: the number of the target on which you will start the tournament.

### Sample Input 1

4 8 7 4 2 6 5 8 1 3

### Sample Output 1

3

### Explanation of Test Case 1

You are the second worst archer. If you start on target 1, you will then go to target 4 and stay there until the end. If you start on target 2 or 4, you will just stay there for the whole tournament. If you start on target 3, you will beat the worst archer and then move to target 2 and stay there.

### Sample Input 2

4 9 2 1 5 8 3 4 7 6

### Sample Output 2

2

### Explanation of Test Case 2

You are the second best archer. The best one is already on target 1 and will stay there for the whole duration of the tournament. Thus, no matter where you start, you will always move from your target, going through all targets from 4 to 1 over and over again. In order for you to end on target 1 after 9 transitions, you have to start on target 2.

**Note**: For a number of tests, worth a total of 60 points, *N* will not exceed 5000.

Also, for some of these tests, worth a total of 20 points, *N* will not exceed 200.

All Submissions

Best Solutions

**Point Value:** 50 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 64M

**Added:** Sep 13, 2009

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...