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 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)