IOI 2012 day2 3- 아이돌 육상 선수권 대회(tournament) > 문제은행 : 정보올림피아드&알고리즘




2598 : 아이돌 육상 선수권 대회(tournament)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
7 회   
시도횟수
25 회   

문제

아이유는 아이돌 육상 선수권 대회에서 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


출력형식

첫 번째 줄에 아이유를 세워야 하는 곳의 번째 수를 출력한다.


입력 예

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

출력 예

1

Hint!

아이유가 1번째 위치에 줄을 서면 달리기 경기는 다음과 같이 진행된다.
첫 번째 경기 : 1 [3 0 2] 4 => 아이유 1등
두 번째 경기 : [1 3] 4 => 아이유 1등
세 번째 경기 : [3 4] => 아이유 2등

아이유는 최대 두 번 1등을 할 수 있고, 두 번 1등을 할 수 있는 위치 중 1번째 위치가 가장 왼쪽에 있다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP