Mex and Cards
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Майк любит играть в карты. На каждой карте в его колоде написано одно целое число от $$$0$$$ до $$$n-1$$$. Изначально колода содержит $$$a_i$$$ карт номиналом $$$i$$$.

Сегодня Майк изучает концепцию mex. Мех набора целых чисел — это наименьшее неотрицательное целое число, не принадлежащее набору. Например, $$$\operatorname{mex}(\{4, 1, 4, 12, 0, 7, 0, 0, 5\}) = 2$$$.

Майк разложит все карты в своей колоде на непустые стопки. Каждая карта должна принадлежать ровно одной стопке. Затем он находит mex значений карт в каждой стопке и складывает их все вместе. Майк хочет найти распределение, которое максимизирует эту сумму.

Более того, с колодой происходит последовательно $$$q$$$ модификаций: иногда в колоду добавляется новая карта, а иногда карта из колоды удаляется. Майк хочет найти распределение с максимальной суммой mex для всех последовательностей: до первой модификации и после первых $$$i$$$ модификаций для каждого $$$i = 1, 2, \ldots, q$$$.

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

Первая строка содержит одно целое число $$$n$$$ — диапазон номиналов карт ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_0, a_1, \ldots, a_{n-1}$$$ — количество карт достоинством $$$0, 1, \ldots, n-1$$$ в колоде изначально ($$$0 \le a_i \le 10^6$$$).

В третьей строке записано одно целое число $$$q$$$ — количество модификаций колоды ($$$0 \le q \le 2 \cdot 10^5$$$).

$$$i$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$p_i$$$ и $$$v_i$$$, описывающих $$$i$$$-ю модификацию ($$$1 \le p_i \le 2$$$; $$$0 \le v_i < n$$$) . Если $$$p_i = 1$$$, в колоду добавляется новая карта номиналом $$$v_i$$$. Если $$$p_i = 2$$$, из колоды удаляется карта номиналом $$$v_i$$$.

Гарантируется, что если $$$p_i = 2$$$, то в колоде есть хотя бы одна карта со значением $$$v_i$$$ непосредственно перед $$$i$$$-й модификацией.

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

Выведите $$$q+1$$$ целое число — максимально возможную сумму mex для некоторого допустимого распределения всех карт по стопкам после первых $$$0, 1, \ldots, q$$$ модификаций колоды.

Пример

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

    5
    2 1 3 0 2
    6
    1 0
    1 1
    2 4
    1 3
    2 1
    2 1

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

    4
    5
    7
    7
    9
    7
    3

Примечание

Для исходной колоды примера одним из лучших распределений является распределение карт со значениями $$$0$$$ и $$$2$$$ в одну стопку, карт со значениями $$$0, 1, 2, 2, 4$$$ в другую стопку, а карту номиналом $$$4$$$ в третью стопку. Сумма mex в этом распределении равна $$$\operatorname{mex}(\{0, 2\}) + \operatorname{mex}(\{0, 1, 2, 2, 4\}) + \operatorname{mex} (\{4\}) = 1 + 3 + 0 = 4$$$.