{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Михаил Мирзаянов\\
         Разработка: & Геннадий Короткевич\\
     \end{tabular}
}

Поймём, как посчитать максимальную сумму mex-ов.

Во-первых, нет смысла делать больше $a_0$ кучек карт~--- для того, чтобы у кучки был положительный mex, в ней должна быть хотя бы одна карта со значением $0$. В то же время, нет смысла класть две карты со значением $0$ в одну кучку~--- всегда можно выделить одну из этих карт в новую кучку с mex $= 1$, улучшив ответ. Значит, мы будем делать ровно $a_0$ кучек.

С картами со значением $1$ ситуация похожая. Если $a_1 < a_0$, положим все карты со значением $1$ в разные кучки. Тогда у $a_0 - a_1$ кучек значение mex зафиксируется на $1$, и его больше нельзя будет улучшить. Остальные же $a_1$ кучек можно будет продолжать. Если же $a_1 \ge a_0$, то положим по одной карте со значением $1$ в каждую кучку, а остальные~--- куда угодно. Тогда все $a_0$ кучек можно будет использовать дальше.

Легко понять, что такая жадная стратегия будет оптимальной. При этом для любого $k = 0, 1, \ldots, n-1$ значение $mex > k$ будут иметь $\min(a_0, a_1, \ldots, a_k)$ кучек. Следовательно, ответ на задачу равен сумме префиксных минимумов в массиве $a$:
\begin{center}
$a_0 + \min(a_0, a_1) + \min(a_0, a_1, a_2) + \ldots + \min(a_0, a_1, \ldots, a_{n - 1})$.
\end{center}

Как обрабатывать изменения? Пусть мы добавили новую карту со значением $v$, и таким образом число карт $a_v$ со значением $v$ увеличилось с $x$ до $x+1$. Есть два случая:
\begin{itemize}
\item Если $\min(a_0, a_1, \ldots, a_{v-1}) \le x$, то ни одного префиксного минимума от увеличения $a_v$ не изменится.
\item Если $\min(a_0, a_1, \ldots, a_{v-1}) > x$, то префиксный минимум на отрезке $[a_0, a_1, \ldots, a_v]$ увеличится на $1$, со значения $x$ до значения $x+1$. Но также могут увеличиться и несколько следующих префиксных минимумов. Найдём ближайшую позицию $i > v$ такую, что $a_i \le x$. Тогда минимум на префиксе $[a_0, a_1, \ldots, a_{i-1}]$ ещё увеличится, а на префиксе $[a_0, a_1, \ldots, a_i]$~--- уже нет. Так как ответ на задачу равен сумме префиксных минимумов, то всего ответ на задачу увеличится ровно на $i - v$.
\end{itemize}

При удалении карты со значением $v$ и уменьшением $a_v$ с $x+1$ до $x$ все действия симметричны, только вместо слова ``увеличение'' в предыдущем абзаце следует читать ``уменьшение''.

Чтобы быстро искать первую позицию со значением не более $x$ в изменяющемся массиве, можно использовать спуск по дереву отрезков на минимум. Сложность решения составит $O((n + q) \log n)$.