마상시합 토너먼트

$N$명의 기사가 참가하는 마상시합 토너먼트가 열린다. 기사들은 처음에 한 줄로 서며, 줄의 앞에서부터 선 순서대로 $0$번부터 $N-1$번까지 번호가 매겨진다.

각 라운드는 두 위치 $S$와 $E$를 부르며 시작한다 ($0 \le S < E \le (\text{현재 줄의 길이}) - 1$). 현재 위치가 $S$부터 $E$까지인 모든 기사가 겨루어 그중 정확히 한 명이 승리한다. 승자는 다시 줄로 돌아가고 패자들은 빠지며, 남은 기사들은 상대 순서를 유지한 채 $0$번 쪽으로 이동해 빈자리를 채운다. 따라서 승자는 위치 $S$에 서게 되고, 남은 기사들은 $0$번부터 (이전 길이) $-(E-S)-1$번까지 다시 번호가 매겨진다. 다음 라운드도 같은 방식으로 진행되며, 마지막 한 명이 남을 때까지 계속된다.

모든 기사의 실력은 서로 다르며 $0$부터 $N-1$까지의 정수로 주어진다 (값이 클수록 실력이 좋다). $C$개 라운드에서 불릴 위치 범위는 미리 모두 알려져 있고, 각 라운드에서는 참가자 중 실력이 가장 높은 기사가 항상 이긴다.

$N$명의 기사 중 $N-1$명은 이미 도착해 줄을 서 있고, 가장 인기 있는 기사 한 명만 아직 도착하지 않았다. 늦게 온 기사의 실력은 $R$이다. 축제를 최대한 즐겁게 만들기 위해, 이 기사가 이기는 라운드의 수가 가장 많아지도록 그를 배치하고 싶다. 이 기사가 참여하지 않는 라운드는 무관하며, 그가 참여해서 이기는 라운드의 수만이 중요하다.

예를 들어 현재 줄의 실력이 $[1, 3, 0, 2, 4]$이고 한 라운드가 $(S, E) = (0, 2)$를 부르면, 위치 $0, 1, 2$의 기사들(실력 $1, 3, 0$)이 겨루어 실력 $3$인 기사가 이기고, 줄은 $[3, 2, 4]$가 된다.

입력으로 다음이 주어진다.

• $N$: 기사의 총수 ($1 \le N \le 100{,}000$).
• $C$: 라운드의 수 ($1 \le C \le N-1$).
• $R$: 늦게 온 기사의 실력. $R$을 포함한 모든 실력은 $0$부터 $N-1$까지의 서로 다른 정수다.
• $K$: 이미 서 있는 $N-1$명 기사의 실력을 줄에 선 순서대로 담은 배열.
• $S$와 $E$: 크기가 $C$인 배열. $0 \le i \le C-1$인 각 $i$에 대해 $i+1$번째 라운드는 현재 위치가 $S[i]$부터 $E[i]$까지인 기사들이 참여한다. 모든 $i$에서 $S[i] < E[i]$이고, $E[i]$는 그 라운드가 시작할 때 줄에 있는 기사 수보다 작으며, $C$개 라운드가 모두 끝나면 정확히 한 명만 남는 것이 보장된다.

늦게 온 기사가 이기는 라운드 수가 최대가 되도록 그를 배치할 최적의 위치 $P$ ($0 \le P \le N-1$)를 구하라. 최적의 위치가 여러 개이면 가장 작은 값을 택한다. 여기서 $P$는 배치 후 늦게 온 기사의 위치, 즉 그 앞에 서 있는 기사의 수다. $P = 0$이면 맨 앞, $P = N-1$이면 맨 뒤에 서는 것을 뜻한다.

첫째 줄에 $N$, $C$, $R$이 주어진다. 다음 $N-1$개의 줄에는 각각 $K[i]$의 값이 하나씩 주어진다. 이어지는 $C$개의 줄에는 각각 $S[i]$와 $E[i]$가 주어진다.

늦게 온 기사를 배치할 최적의 위치 $P$ 중 가장 작은 값을 한 줄에 출력한다.