Do you know why the fourth floor is locked and the elevator does not stop there? Because in fact the fourth, locked, floor, where the elevator does not stop, contains an infinite number of rooms, numbered with natural numbers. On this floor children regularly come, each of whom has previously chosen which room he wants to occupy. If the selected room is vacant, the child occupies it, otherwise it occupies the first free room with a larger number. In addition, some children leave in the middle of the recreation. Immediately after the departure of the child, his room becomes available.

Simulate the work of the teachers responsible for the fourth floor, and learn how to quickly tell the visiting children what room they should occupy.

Input

First line contains one integer n - the number of arrivals and departures occurring during the recreation (n ≤ 100000). Next n lines contains the information about LKSH students. Number a > 0 means that the child arrived and wants to occupy the room with number a (a ≤ 106). Number a < 0 means that the child left the room number |a| (It is guaranteed that this room was not empty).

Output

For each coming student print the room number where he will live.