시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 420 | 110 | 95 | 30.159% |
지환이는 업무에 치여 산다. 하루에도 몇 건인지도 모를 정도로 많은 업무가 들어온다.
각 업무는 양의 정수로 표현되는 고유번호 $p_i$ ($1 \leq p_i \leq N$)를 가지고 있으며, 고유번호는 모두 다르다.
아, 일이 또 추가되었다. 참다못한 지환이는 스케줄링을 하기 위한 기계 ‘지환봇 스케줄러’를 만들었지만, 그마저도 제대로 만들지는 못한 것 같다. '지환봇 스케줄러'는 기본적으로는 스택(stack) 구조, 즉 제일 나중에 들어간 업무가 제일 먼저 처리되는(LIFO, Last in First out) 특성을 가지고 있다.
기본적인 특성과 더불어, '지환봇 스케줄러'에게 할 수 있는 명령은 다음과 같다.
'지환봇 스케줄러'에 필요 없어 보이는 기능이 있는 것 같지만, 지환이는 이전보다 효과적인 업무처리를 기대할 수 있을 것 같다. 주어진 $Q$개의 명령을 순서대로 처리한 후, $k$번째로 처리해야 하는 업무의 고유번호는 무엇일까?
첫째 줄에 업무의 고유번호의 범위 제한 $N$과 명령 횟수 $Q$, $k$가 주어진다. ($1\leq N,Q \leq 100\,000,\ 1\leq k \leq$ '0번 명령의 등장 횟수')
둘째 줄부터 $Q$개 줄에 걸쳐 명령에 대한 정보가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
모든 명령을 순서대로 적용한 후, $k$번째로 처리하게 될 업무의 고유번호를 출력한다.
5 7 5 0 1 0 2 0 3 1 0 4 0 5 2
5