Description

In 1491, Duke Milan Lodovico Sforza asked Leonardo to prepare the celebration for his wedding with Beatrice d'Este. The celebration included a grand three-day jousting tournament, but the most popular knight was late...

In a jousting tournament, $N$ knights are initially lined up in a row and numbered from $0$ to $N-1$ according to their positions. In each round, the host calls two positions $S$ and $E$ (where $0 \le S < E \le N - 1$). All knights whose positions are between $S$ and $E$ (inclusive) start jousting. The final winner stays in the tournament and returns to his original position, while all losers leave the tournament. After that, the remaining knights close ranks in their original order, filling the empty positions. Their positions are then renumbered from $0$ to $N - (E - S) - 1$. The host then proceeds to the next round, until only one knight remains.

Leonardo knows that all knights have different strengths, ranging from $0$ (weakest) to $N-1$ (strongest). He also knows exactly what commands the host will give for $C$ rounds, because Leonardo can do anything. He is also sure that in each round, the knight with the greatest strength will win.

Among the $N$ knights, $N-1$ knights have already lined up, but the most popular knight has not appeared yet. This late knight has strength $R$. To make the tournament reach its climax, Leonardo wants this knight to show his style well, so he wants to insert him into a position such that he can win the maximum number of rounds. Note that we do not care about rounds that do not involve this knight. We only care about rounds that include this knight and are won by him.

Example

Suppose there are $5$ knights, and $4$ of them have already lined up with strengths $[1,0,2,4]$. The late knight has strength $3$. Suppose there will be $3$ rounds, and the host plans to call positions $(S,E)$ as $(1, 3)$, $(0, 1)$, $(0, 1)$.

If Leonardo inserts the late knight into the first position, then the strengths become $[3, 1, 0, 2, 4]$. In the first round, the knights at positions $1,2,3$ participate, with strengths $1,0,2$, so the knight with strength $2$ wins. After this round, the new sequence of strengths becomes $[3, 2, 4]$. In the next round, the knights with strengths $3$ and $2$ (positions $0,1$) compete, and the knight with strength $3$ wins. The sequence then becomes $[3,4]$. In the last round (positions $0,1$), the knight with strength $4$ wins. Therefore, the late knight wins only one round (the second round).

If Leonardo inserts the late knight between the knights with strengths $1$ and $0$, then the strengths become $[1,3,0,2,4]$. This time, in the first round the participating strengths are $3,0,2$. The knight with strength $3$ wins, and the sequence becomes $[1,3,4]$. In the second round, the knight with strength $1$ faces the knight with strength $3$, and the knight with strength $3$ wins. In the last round, the sequence becomes $[3,4]$, and the knight with strength $4$ wins. In this arrangement, the late knight wins two rounds. This is actually the best position, because no other position allows the late knight to win more than two rounds.

Your task is to write a program to help the late knight choose the best position so that he can win the maximum number of rounds, meeting Leonardo’s expectations.

Input Format

• The first line contains $3$ integers $N$, $C$, $R$, where $N$ is the number of knights, $C$ is the number of rounds the host will conduct, and $R$ is the strength of the late knight.
• The second line contains $N-1$ integers $K[0],K[1],\cdots,K[N-2]$, representing the strengths of the $N-1$ knights already lined up.
• The third line contains $2C$ integers $S[0],E[0],S[1],E[1],\cdots,S[C-1],E[C-1]$. For $0 \le i \le C-1$, in round $i+1$ the host makes the knights from position $S[i]$ to position $E[i]$ (inclusive) compete. You may assume that for each $i$, $S[i] < E[i]$.

Output Format

Output one line: the position that allows the late knight to win the maximum number of rounds. If there are multiple optimal positions, output the smallest index.

5 3 3
1 0 2 4
1 3
0 1
0 1

1

Hint

For $100\%$ of the data, $1 \le N \le 10^5$, $1 \le C \le N-1$. In round $i+1$, $E[i]$ is less than the number of knights remaining in that round. After the $C$ commands, there will be only one knight left.

Translated by ChatGPT 5