학생 식당

시간 제한1초메모리 제한512 MB

요약

학생들은 도착 순서대로 번호가 매겨지고 줄 맨 뒤에 서거나 앞선 학생 앞으로 새치기합니다. 새치기할 때마다 그 학생의 현재 위치를 1부터 셉니다.

난이도: 보통10점 중 6점
유형: 구현, 연결 리스트, 이분 탐색
정답자: 아직 제출이 없습니다

문제

학생 식당이 문을 열기도 전에 입구 앞에 줄이 생긴다. 학생 $n$ 명이 한 명씩 줄에 도착하며, 도착하는 순서대로 1번부터 $n$ 번까지 번호가 붙는다. 줄을 관찰한 결과 일부 학생은 원래 그래야 하는 것처럼 줄의 맨 뒤에 서지 않고, 자기 친구들 옆에 무례하게 끼어들고 친구들은 (마찬가지로 무례하게) 그 학생을 자기 앞으로 들여보낸다.

학생들의 도착을 입력받아 다음을 처리하는 프로그램을 작성하라. 도착은 두 가지다.

학생 $i$ 가 줄의 맨 뒤에 도착했다.
학생 $i$ 가 학생 $j$ 앞으로 끼어들었다.

각 끼어들기(타입 B)에 대해, 그 순간 줄의 맨 앞부터 세어 학생 $i$ 의 위치를 출력한다.

입력

첫째 줄에 자연수 $n$ ( $2 \le n \le 300\,000$ )이 주어진다. 이는 학생 수다.

다음 $n$ 개 줄은 학생 식당 앞 줄에 한 학생이 도착한 것을 나타낸다. $i$ 번째 줄에 숫자 0이 적혀 있으면 타입 A의 도착이다. 그렇지 않으면 $i$ 번째 줄에 숫자 $j$ ( $1 \le j < i$ )가 적혀 있고, 타입 B의 도착이다. 적어도 하나의 도착은 타입 B이다.

출력

각 타입 B 도착에 대해, 방금 줄에 끼어든 학생의 위치를 한 줄에 하나씩 출력한다.

힌트

이 예시에서 줄의 상태는 다음과 같다.

(1),
(1, 2),
(1, 3, 2), 위치 2를 출력,
(1, 4, 3, 2), 위치 2를 출력,
(1, 4, 3, 5, 2), 위치 4를 출력.

예제1

예제 1
입력
```
5
0
0
2
3
2
```
예상 출력
```
2
2
4
```