\begin{problem}{Mex and Cards}{стандартный ввод}{стандартный вывод}{3 секунды}{512 мегабайт}

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

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

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

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

\InputFile
Первая строка содержит одно целое число $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$-й модификацией.

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

\Example

\begin{example}
\exmpfile{example.01}{example.01.a}%
\end{example}

\Note
Для исходной колоды примера одним из лучших распределений является распределение карт со значениями $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$.

\end{problem}

