One puts the sheets of paper with numbers into the black box. Each sheet contains exactly one integer. Sometimes certain sheets disappear from the box. After each event (when the sheet is put into the box, or when the sheet disappears from the box), you need to print the number that occurs most often on sheets that are currently in the box. If multiple such numbers exist, print the smallest.

Input

The first line contains the number of events n (1 ≤ n ≤ 2 *105). Each of the next n lines describes one event:

• + x - the sheet with number x (1 ≤ x ≤ 106) is put into the box;
• - x - the sheet with number x disappeared from the box (it is guaranteed that the box contains at least one sheet with number x).

Output

Print n lines - one line for each event. Print in each line the answer to the problem. If after some event the box is empty, print 0.

disappeared