{"scoring":null,"notes":"Для исходной колоды примера одним из лучших распределений является распределение карт со значениями $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$.","legend":"Майк любит играть в карты. На каждой карте в его колоде написано одно целое число от $0$ до $n-1$. Изначально колода содержит $a_i$ карт номиналом $i$.\r\n\r\nСегодня Майк изучает концепцию \\textit{mex}. Мех набора целых чисел --- это наименьшее неотрицательное целое число, не принадлежащее набору. Например, $\\operatorname{mex}(\\{4, 1, 4, 12, 0, 7, 0, 0, 5\\}) = 2$.\r\n\r\nМайк разложит все карты в своей колоде на непустые стопки. Каждая карта должна принадлежать ровно одной стопке. Затем он находит mex значений карт в каждой стопке и складывает их все вместе. Майк хочет найти распределение, которое максимизирует эту сумму.\r\n\r\nБолее того, с колодой происходит последовательно $q$ модификаций: иногда в колоду добавляется новая карта, а иногда карта из колоды удаляется. Майк хочет найти распределение с максимальной суммой mex для всех последовательностей: до первой модификации и после первых $i$ модификаций для каждого $i = 1, 2, \\ldots, q$.","authorLogin":"tourist","language":"russian","timeLimit":3000,"output":"Выведите $q+1$ целое число~--- максимально возможную сумму mex для некоторого допустимого распределения всех карт по стопкам после первых $0, 1, \\ldots, q$ модификаций колоды.","inputFile":"stdin","outputFile":"stdout","input":"Первая строка содержит одно целое число $n$~ --- диапазон номиналов карт ($1 \\le n \\le 2 \\cdot 10^5$).\r\n\r\nВторая строка содержит $n$ целых чисел $a_0, a_1, \\ldots, a_{n-1}$~ --- количество карт достоинством $0, 1, \\ldots, n-1$ в колоде изначально ($0 \\le a_i \\le 10^6$).\r\n\r\nВ третьей строке записано одно целое число $q$~ --- количество модификаций колоды ($0 \\le q \\le 2 \\cdot 10^5$).\r\n\r\n$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$.\r\n\r\nГарантируется, что если $p_i = 2$, то в колоде есть хотя бы одна карта со значением $v_i$ непосредственно перед $i$-й модификацией.","authorName":"Gennady Korotkevich","sampleTests":[{"output":"4\r\n5\r\n7\r\n7\r\n9\r\n7\r\n3\r\n","input":"5\r\n2 1 3 0 2\r\n6\r\n1 0\r\n1 1\r\n2 4\r\n1 3\r\n2 1\r\n2 1\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"Mex and Cards","interaction":null,"memoryLimit":536870912,"tutorial":""}