У Булата есть мультимножество целых чисел, которое изначально пусто. Ему нужно обработать $$$q$$$ запросов. Запросы приходят либо на добавление, либо на удаление одного целого числа из мультимножества. После каждого запроса ему необходимо вычислить максимальный возможный МEX мультимножества, который он может получить, если может применять следующие операции. С помощью одной операции можно взять элемент $$$x$$$, который встречается в мультимножестве как минимум дважды, удалить один из них и добавить либо $$$x-1$$$, либо $$$x+1$$$. Эти операции не влияют на мультимножество для следующего запроса.
MEX — это операция, которая означает «минимальный отсутствующий»: MEX мультимножества чисел равен наименьшему неотрицательному целому числу, которого нет в мультимножестве. Например, $$$\text{mex}(\{0,1,1,2,4,4\})=3$$$. Однако, в данной задаче с помощью разрешенных операций мультимножество может быть преобразовано в $$$\{0,1,2,3,4,5\}$$$, у которого MEX уже равен $$$6$$$.
Помогите Булату обработать запросы.
Первая строка содержит единственное целое число $$$q$$$ ($$$1 \leq q \leq 10^6$$$), количество запросов. Следующие $$$q$$$ строк описывают запросы. $$$i$$$-я из них содержит два целых числа $$$t_i$$$, $$$a_i$$$ ($$$1 \leq t_i \leq 2$$$, $$$0 \leq a_i \leq 10^6$$$):
После каждого из запросов выведите в отдельную строку единственное число, максимально возможное значение MEX мультимножества, если преобразовать его с помощью разрешенных операций.
9 1 0 1 1 1 1 1 2 1 4 1 4 2 1 2 2 1 4
1 2 3 4 5 6 5 2 5
