Background

IOI 2009 D1T1.

Problem Description

An archery competition is taking place. There are $N$ targets arranged on a straight line, numbered from $1$ to $N$ from left to right. There are $2N$ players, and at any moment there are two players at each target. Each round of the competition proceeds as follows:

• The two players at the same target play a match to decide a winner. Then all players move according to these rules:

  • The winners at targets $2$ to $N$ move to the target immediately to their left (that is, to targets $1\sim N - 1$, respectively).
  • The losers at targets $2$ to $N$, as well as the winner at target $1$, stay at the same target.
  • The loser at target $1$ moves to target $N$.

The competition lasts for a total of $R$ rounds, and the number of rounds is at least the number of players, i.e. $R\geq 2N$.

You are the only player who arrives on time. The other $2N - 1$ players have already arrived and formed a line, and now you need to insert yourself into this line. After you join the line, the first two players in the queue (the two leftmost players) will correspond to target $1$, the next two players to target $2$, and so on, and the two rightmost players correspond to target $N$.

All $2N$ players (including you) have a numerical skill level, and no two players have the same skill level. At the same target, the player with the smaller value becomes the winner.

After learning the skill levels of all players, you need to find an insertion position so that the target number you end up at is as small as possible. Subject to that, you want your initial target number to be as large as possible.

Task: Write a program that, given the skill levels of all players (including yourself) and the order of your opponents, computes your initial target number to satisfy the goals above.

Input Format

The first line contains two integers $N, R$ separated by a space, representing the number of targets and the number of rounds.

The next $2N$ lines give the players' ranking list $S_1, S_2, \cdots, S_{2N}$. $S_1$ is your rank, and $S_2, S_3, \cdots, S_{2N}$ are the ranks of the other players, in the order they have already lined up (from left to right). $S_k$ is an integer in $1\sim 2N$, where rank $1$ is the best and rank $2N$ is the worst. No two players have the same rank.

Output Format

Output an integer in $1\sim N$, representing the initial target number.

4 8
7
4
2
6
5
8
1
3

3

4 9
2
1
5
8
3
4
7
6

2

Hint

Explanation of the Samples

• Sample 1: You are the second worst player. If you start at target $1$, then you will move to target $4$ next and stay at target $4$ until the end. If you start at target $2$ or target $4$, you will stay there until the end. If you start at target $3$, you will defeat the worst player, then move to target $2$ and stay there.

• Sample 2: You are the player ranked second. The player ranked first is at target $1$ and stays there forever. Therefore, no matter where you start, you will always move in the cycle $4\to 3\to 2\to 1\to 4$. To finally stay at target $1$, you should start at target $2$.

Constraints and Notes

• For $20\%$ of the testdata, $N\leq 200$.
• For $60\%$ of the testdata, $N\leq 5000$.
• For $100\%$ of the testdata, $1\leq N\leq 2\times 10 ^ 5$, $2N\leq R\leq 10 ^ 9$, $1\leq S_k\leq 2N$ and all $S_k$ are distinct.

There are also three groups of hack testdata provided by

Translated by ChatGPT 5