Mex and Cards

Mike enjoys playing with cards. Each card in his deck has a single integer value from $0$ to $n-1$ written on it. Initially the deck contains $a_i$ cards with value $i$.

Today Mike is learning the concept of mex. The mex of a collection of integers is the smallest non-negative integer that does not belong to the collection. For instance, $\operatorname{mex}(\{4, 1, 4, 12, 0, 7, 0, 0, 5\}) = 2$.

Mike will distribute all cards in his deck into non-empty piles. Each card must belong to exactly one pile. He will then find the mex of the card values in each pile and add them all together. Mike wants to find a distribution that maximizes this sum.

A sequence of $q$ modifications happens to the deck. Sometimes a new card is added, and other times a card is removed. Mike wants to find the distribution with the maximum sum of mexes before the first modification and after the first $i$ modifications for every $i = 1, 2, \ldots, q$.

The first line contains a single integer $n$, the range of card values ($1 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_0, a_1, \ldots, a_{n-1}$, the number of cards with value $0, 1, \ldots, n-1$ in the deck initially ($0 \le a_i \le 10^6$).

The third line contains a single integer $q$, the number of deck modifications ($0 \le q \le 2 \cdot 10^5$).

Each of the next $q$ lines contains two integers $p_i$ and $v_i$, describing the $i$-th modification ($1 \le p_i \le 2$, $0 \le v_i < n$). If $p_i = 1$, a new card with value $v_i$ is added to the deck. If $p_i = 2$, a card with value $v_i$ is removed from the deck.

It is guaranteed that if $p_i = 2$, then the deck contains at least one card with value $v_i$ right before the $i$-th modification.

Print $q+1$ integers. The $j$-th integer is the maximum possible sum of mexes for some valid distribution of all cards into piles after the first $j-1$ modifications of the deck ($j = 1, 2, \ldots, q+1$).

In the example test, one of the best distributions for the initial deck is to put the cards with values $0$ and $2$ into one pile, the cards with values $0, 1, 2, 2, 4$ into another pile, and the card with value $4$ into a third pile. The sum of mexes for this distribution is $\operatorname{mex}(\{0, 2\}) + \operatorname{mex}(\{0, 1, 2, 2, 4\}) + \operatorname{mex}(\{4\}) = 1 + 3 + 0 = 4$.