Archery#287

Archery

2 seconds
64 megabytes
Medium

An archery tournament is held according to the following rules. There are targets arranged in a line, numbered from to from left to right (the leftmost target is , the rightmost is ). There are also archers. At any time, two archers stand on each target. Each round proceeds as follows:

- The two archers on each target compete, determining a winner and a loser. Then all archers are rearranged: - Winners on targets to move to the target on their left (i.e., to targets to n-1). - Losers on targets to and the winner on target remain on their targets. - The loser on target moves to target .

The tournament lasts rounds, where r \geq 2n.

You are the only archer to arrive exactly on time. The other 2n-1 archers have already arrived and are in line from left to right. You now insert yourself somewhere in the line. After you take your position, the two leftmost archers start on target , the next two on target , and so on, with the two rightmost on target .

Each archer is assigned a unique rank based on skill; smaller rank is better. No two archers have the same rank. An archer with a smaller rank always wins.

You want to insert yourself so that you finish the tournament on the smallest possible target number. If there is more than one way, you prefer to start on the largest possible target number.

Write a program that, given the ranks of all archers (including you) and the arrangement of your competitors, determines on which target you should start the tournament to achieve your goal.

Input

The first line contains two integers: the number of targets (1 \leq n \leq 200\,000), and the number of rounds (2n \leq r \leq 1\,000\,000\,000), separated by a space.

The next lines contain the ranks of the archers. The first line contains your rank. The remaining 2n-1 lines contain the ranks of the other archers in their current order (from left to right). Each value is an integer between and inclusive. Rank is best, rank is worst. No two archers have the same rank. That is, 1 \leq S_k \leq 2n, where S_k is the -th archer's rank.

Output

Print an integer between and , the number of the target on which you will start the tournament.

Examples

Example 1

Loading
Loading