문제
아이유는 아이돌 육상 선수권 대회에서 100m 달리기로 출전하게 되었다.
아이돌 육상 선수권 대회는 다음과 같은 규칙으로 이루어진다.
(1) 1번째 아이돌부터 N번째 아이돌까지 일직선으로 줄을 선다.
각 아이돌들은 어떤 위치에 서도 된다. 그러나 아이돌들은 한 번 줄을 선다면 더 이상 위치를 바꿀 수 없다. (2) PD는 Si 번째 아이돌(자신의 왼쪽에 아이돌이 정확히 Si 명 서 있는 아이돌)에서부터 Ei 번째 아이돌까지 불러서 100m 달리기 경기를 한다.
가장 달리기 실력이 뛰어난 1등만 다시 줄로 돌아오고 나머지 아이돌들은 모두 탈락한다. 탈락한 아이돌들은 재경기를 할 수 없다. (3) PD는 R번의 경기를 한 후 최종 우승자 1명을 결정한다.
N-1명의 아이돌들은 이미 줄을 다 서고 아이유만 줄을 설 차례이다.
그런데 아이유는 방송분량을 최대한 많이 뽑고 싶어 하기 때문에, 달리기 경기에서 최대한 많이 1등을 하려고 한다.
만약 방송분량을 가장 많이 뽑는 위치가 여러 곳인 경우, 아이유는 줄을 서면서 지체하는 것을 싫어하기 때문에 최대한 줄을 왼쪽에 서려고 한다.
아이유는 자신의 달리기 실력, 다른 아이돌들의 달리기 실력, 그리고 Si, Ei 를 전부 알고 있다.
아이유가 당신에게 준 값들을 바탕으로 아이유를 줄의 몇 번째에 세워야 하는지 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 아이돌의 수(아이유 포함) N, 달리기 경기의 수 R, 아이유의 달리기 실력 C가 주어진다. 두 번째 줄에는 현재 줄을 서고 있는 N-1명의 아이돌들의 달리기 실력 Ki 가 주어진다. 세 번째 줄부터 R개의 줄에는 PD가 달리기 경기를 진행하는 범위인 Si 와 Ei 가 주어진다. N명의 아이돌들의 달리기 실력은 모두 다르고, PD가 R번의 경기를 진행한 후에는 정확히 한 명의 아이돌만 남아 있어야 한다.
1 ≤ N ≤ 100,000 0 ≤ C, Ki < N Si < Ei
출력
첫 번째 줄에 아이유를 세워야 하는 곳의 번째 수를 출력한다.
예제1
533
1024
13
01
01
1