다음에 확인할 메시지

문제

사내 메신저에 여러 업무 알림이 도착한다. 담당자는 모든 알림을 도착한 순서대로 확인하는 대신, 알림에 붙은 중요도를 기준으로 다음에 확인할 알림을 고른다. 메신저는 아직 확인하지 않은 알림을 보관하는 대기함을 관리하며, 처음에는 대기함이 비어 있다. 메신저에 주어지는 명령은 알림 등록과 알림 확인의 두 종류다. 등록 명령에는 1 이상 9 이하의 정수인 중요도가 함께 주어진다. 새 알림의 식별 번호는 그 등록 명령이 전체 명령 중 몇 번째인지를 나타내는 번호다. 명령 번호는 1부터 시작하므로 서로 다른 알림의 식별 번호는 항상 다르다. 확인 명령도 명령 번호를 하나 차지한다. 확인 명령이 실행되면 대기함에서 중요도가 가장 높은 알림 하나를 선택한다. 그러한 알림이 여러 개이면 식별 번호가 가장 작은 알림을 선택한다. 이는 같은 중요도의 알림 중 먼저 등록된 것을 선택한다는 뜻이다. 선택한 알림의 식별 번호를 기록하고, 그 알림을 대기함에서 즉시 제거한다. 이미 제거한 알림은 이후의 확인 명령에서 다시 선택할 수 없다. 대기함이 비어 있을 때 확인 명령이 실행되면 0을 기록한다. 이 명령은 나중에 등록될 알림에 영향을 주지 않는다. 등록 명령을 실행할 때는 아무것도 기록하지 않는다. 모든 명령은 입력에 주어진 순서대로 하나씩 실행되며, 두 명령이 동시에 실행되는 경우는 없다. 모든 명령을 처리하면서 확인 명령마다 기록되는 값을 순서대로 출력하는 프로그램을 작성한다. 마지막 명령까지 처리한 뒤 대기함에 남은 알림을 따로 확인하거나 출력하지 않는다.

입력

첫째 줄에 명령의 수 N이 주어진다. N은 1 이상 100,000 이하의 정수다.
다음 N개의 줄에 명령이 하나씩 주어진다. 등록 명령은 두 정수 `1 p`로 주어지며, p는 1 이상 9 이하의 중요도다. 확인 명령은 정수 `2` 하나로 주어진다.
전체 명령 중 확인 명령이 적어도 하나 존재한다.

출력

확인 명령마다 기록되는 정수를 한 줄에 하나씩 출력한다. 대기함이 비어 있으면 0을 출력한다.

8
2
1 3
1 5
1 5
2
1 8
2
2

0
3
6
4

5
1 2
2
2
1 1
2

1
0
4

출처: Devin.KR 자체 제작