- Time limit: 1.00 s
- Memory limit: 512 MB
n players numbered 1,2,\dots,n are standing on a log that is x meters long. The players will be taking turns from left to right and the leftmost player comes after the rightmost one. On their turn a player has to move one meter to the left or right. If the player is blocked on both sides by other players they fall off the log immediately and die. The same obviously also happens if they step off the log. The last player standing wins. It can be proven that the game has a winner if all players play optimally. Given the positions of the players, find that winner. In the beginning the i-th player stands a_i meters from the left corner of the log.
Input
The first line contains two integers n and x.
The second line contains n integers a_1,\,a_2,\ldots,\,a_n.
Output
Print the number of the winning player.
Constraints
- 1 \leq n \leq 10^5
- 1 \leq n \leq x \leq 10^9
- 1 \leq a_i \leq x
- a_i < a_j if i < j
Example 1
Input:
2 3 1 2
Output:
2
Explanation:
Player 1 has to move first. The only option they have is to step to left off the log, so player 2 wins.
Example 2
Input:
2 4 1 3
Explanation:
First player 1 takes one step right.
Player 2 has to move right too.
Player 1 takes one step right.
Player 2 has to step right off the log.
Output:
1
Example 3
Input:
5 18 1 5 7 16 18
Output:
4