У чорний ящик кладуть аркуші з написаними на них числами. На кожному аркуші - рівно одне ціле число. Іноді деякі аркуші щезають з ящика. Після кожної події (коли у ящик поклали аркуш або коли з ящика щез аркуш), потрібно вивести число, яке зустрічається частіше всього на аркушах, які знаходяться у даний момент в ящику. Якщо таких чисел декілька, виведіть найменше.

Вхідні дані

Перший рядок містить кількість подій n (1 ≤ n ≤ 2 *105). Кожен з наступних n рядків містить опис однієї події:

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

Вихідні дані

Вивести вточності n рядків - по одному для кожної події. Кожен рядок повинен містити рівно одне число - відповідь до задачі. Якщо після якоїсь події ящик виявився порожнім, потрібно вивести 0.