Student Canteen

Time limit1sMemory limit512 MB

Summary

Students numbered by arrival either join the back of a queue or cut in right ahead of an earlier student; report each cutter's 1-indexed position at that moment.

Level: Medium6 of 10
Topics: Implementation, Linked list, Binary search
Solved: No attempts yet

Problem

Even before the student canteen opens, a queue forms in front of it. Students arrive at the queue one by one, and they are numbered from 1 to $n$ in the order they arrive. Watching the queue, you notice that some students do not go to the back of the queue the way they should. Instead, they rudely cut in next to their friends, who (just as rudely) let them pass ahead.

Write a program that reads the arrivals of students, which can be:

student $i$ arrived at the back of the queue, or
student $i$ cut in ahead of student $j$ .

For every cut-in (type B), print the position of student $i$ at that moment, counting from the front of the queue.

Input

The first line contains a positive integer $n$ ( $2 \le n \le 300\,000$ ), the number of students.

Each of the following $n$ lines describes one student's arrival at the queue in front of the canteen. If the $i$ -th line contains the number 0, this is an arrival of type A. Otherwise the $i$ -th line contains the number $j$ ( $1 \le j < i$ ), and this is an arrival of type B. At least one arrival is of type B.

Output

For each arrival of type B, print the requested position of the student who has just cut into the queue, one per line.

Hint

The state of the queue in this example:

(1),
(1, 2),
(1, 3, 2), we print position 2,
(1, 4, 3, 2), we print position 2,
(1, 4, 3, 5, 2), we print position 4.

Examples1

Example 1
Input
```
5
0
0
2
3
2
```
Expected output
```
2
2
4
```