Майк любит играть в карты. На каждой карте в его колоде написано одно целое число от $$$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$$$.