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