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 \textit{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.

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