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

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

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

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

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

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