August 8 – 15, Plovdiv, Bulgaria

Contest Day 1 - Archery

English 1.1

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.

TASK
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.

EXAMPLES

Sample Input

Sample Output
4 8
7
4
2
6
5
8
1
3
3

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

Sample Output
4 9
2
1
5
8
3
4
7
6
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.

1 ≤ N ≤ 200,000

The number of targets; also equal to half the number of archers
2N ≤ R ≤ 1,000,000,000 The number of tournament rounds
1 ≤ Sk ≤ 2N

The rank of archer k

August 8 – 15, Plovdiv, Bulgaria

Contest Day 1 - Archery

English 1.1

Your program must read from standard input the following data:
• The first line contains the integers N and R, separated by a space.
• The next 2N 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 2N lines contains
a single integer between 1 and 2N inclusive. A rank of 1 is the best and a rank of 2N is the
worst. No two archers have the same rank.

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.

GRADING
For a number of tests, worth a total of 60 points, N will not exceed 5,000.
Also, for some of these tests, worth a total of 20 points, N will not exceed 200.

생성자가 기록되지 않았습니다.

출처 IOI 2009