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
The first line contains two integers - the number of targets n (1 ≤ n ≤ 200,000) that equals to half the number of archers, and the number of tournament rounds r (2*n ≤ r ≤ 1,000,000,000), separated with 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. It is known that 1 ≤ S_k ≤ 2*n, where S_k is the rank of an archer k.
Output
Print a single integer between 1 and n inclusive: the number of the target on which you will start the tournament.