Jousting Tournament

A jousting tournament is held with $N$ knights. The knights first stand in a single line and, from the front, are numbered $0$ to $N-1$ in the order they stand.

A round begins by announcing two positions $S$ and $E$ with $0 \le S < E \le (\text{current line length}) - 1$. Every knight currently standing at positions $S$ through $E$ (inclusive) competes, and exactly one of them wins. The winner goes back into the line while the losers drop out; the remaining knights then move toward position $0$, keeping their relative order, to close the gaps, so the winner ends up at position $S$. The line is thus renumbered $0$ to (previous length) $-(E-S)-1$. The next round works the same way, and rounds continue until a single knight is left.

Every knight has a distinct skill, given as an integer from $0$ to $N-1$ (a larger value means a stronger knight). The position ranges of all $C$ rounds are known in advance, and in every round the competitor with the highest skill always wins.

Of the $N$ knights, $N-1$ have already arrived and are standing in line; only the most popular knight has not arrived yet. The late knight has skill $R$. To make the festival as exciting as possible, we want to insert this knight at the position that maximizes the number of rounds it wins. Rounds in which the late knight does not take part are irrelevant — only the rounds it enters and wins are counted.

For example, if the current line has skills $[1, 3, 0, 2, 4]$ and a round announces $(S, E) = (0, 2)$, then the knights at positions $0, 1, 2$ (skills $1, 3, 0$) compete, the skill-$3$ knight wins, and the line becomes $[3, 2, 4]$.

You are given:

• $N$: the total number of knights ($1 \le N \le 100{,}000$).
• $C$: the number of rounds ($1 \le C \le N-1$).
• $R$: the skill of the late knight. All skills, including $R$, are distinct integers from $0$ to $N-1$.
• $K$: an array of $N-1$ integers, the skills of the already-present knights in line order.
• $S$ and $E$: arrays of length $C$. For each $i$ with $0 \le i \le C-1$, round $i+1$ involves the knights currently at positions $S[i]$ through $E[i]$. It is guaranteed that $S[i] < E[i]$, that $E[i]$ is smaller than the number of knights in line when that round starts, and that exactly one knight remains after all $C$ rounds.

Find the best position $P$ ($0 \le P \le N-1$) at which to insert the late knight so that the number of rounds it wins is as large as possible. If several positions are optimal, choose the smallest. Here $P$ is the late knight's position after insertion, i.e. the number of knights standing in front of it: $P = 0$ places it at the very front, and $P = N-1$ places it at the very back.

The first line contains $N$, $C$, and $R$. Each of the next $N-1$ lines contains one value $K[i]$. Each of the following $C$ lines contains $S[i]$ and $E[i]$.

Print $P$, the smallest optimal insertion position for the late knight, on a single line.