Problem description


Mex
(mex)
Memory limit: 64 MB
Time limit: 4.50 s

Jasio przygotowuje się do zawodów algorytmicznych. Ostatnio uczy się podstaw teorii gier. Poznał funkcję mex przydatną w obliczaniu tak zwanych nimberów dla pozycji w grach. Funkcja mex dla multizbioru nieujemnych liczb całkowitych oblicza najmniejszą nieujemną liczbę całkowitą, która nie należy do podanego multizbioru. Na przykład mex({1,0,4}) = 2, mex({1,2,3}) = 0, mex({0,1,2}) = 3.

Jasio ma niestety problemy z obliczaniem tej funkcji. Chciał napisać program, który będzie umożliwiał następujące operacje:

  • dodawanie liczb do multizbioru,

  • usuwanie liczb z multizbioru,

  • obliczanie wartości funkcji . Pomóż mu!

Napisz program, który: wczyta operacje do programu, wyznaczy odpowiedzi dla wszystkich zapytań o wartość funkcji mex i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę operacji na początkowo pustym multizbiorze. W kolejnych Q wierszach znajduje się opis kolejnych operacji. Opis każdej z nich może być następujący:

  • znak +, pojedynczy odstęp oraz nieujemna liczba całkowita xi (operacja dodania do multizbioru liczby xi),

  • znak -, pojedynczy odstęp oraz nieujemna liczba całkowita xi (operacja usunięcia z multizbioru jednej kopii liczby xi),

  • znak ? (zapytanie o wynik funkcji mex).

Gwarantowane jest, że nigdy nie będzie usuwany element, którego w zbiorze nie ma. Gwarantowane jest też, że nigdy nie nastąpi zapytanie o mex pustego zbioru.

Wyjście

Twój program powinien wypisać po jednym wierszu dla każdej operacji typu ?, zgodnie z kolejnością operacji na wejściu. W wierszu powinna się znaleźć jedna nieujemna liczba całkowita – wynik funkcji mex dla bieżącego stanu multizbioru.

Ograniczenia

1 ≤ Q ≤ 1 000 000, 0 ≤ xi ≤ 109.

Przykład

Input Output
10
+ 3
+ 0
+ 1
?
+ 1
- 1
+ 2
?
- 1
?
2
4
1