e-olymp
Задачи

Чёрный ящик

Чёрный ящик

В черный ящик кладутся листки с написанными на них числами. На каждом листке - ровно одно целое число. Иногда некоторые листки исчезают из ящика. После каждого события (когда в ящик положили листок, или когда из ящика исчез листок), нужно вывести число, которое встречается чаще всего на листках, находящихся в данный момент в ящике. Если таких чисел несколько, выведите наименьшее.

Входные данные

Первая строка содержит количество событий n (1n2 *105). Каждая из следующих n строк содержит описание одного события:

  • + x - положен листок с числом x (1x106);
  • - x - исчез листок с числом x (гарантируется, что в ящике был хотя бы один листок с числом x).

Выходные данные

Вывести в точности n строк - по одной для каждого события. Каждая строка должна содержать одно число - ответ к задаче. Если после какого-то события ящик оказался пуст, следует вывести 0.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
3
+ 1
- 1
+ 2
Выходные данные #1
1
0
2
Источник Открытый личный чемпионат ИГЭУ, Иваново, 20.05.2011