Mike 喜欢玩卡牌。他牌堆中的每张卡牌上都写有一个 $0$ 到 $n-1$ 之间的整数。最初，牌堆中数值为 $i$ 的卡牌有 $a_i$ 张。

今天，Mike 正在学习 mex 的概念。一个整数集合的 mex 是指不属于该集合的最小非负整数。例如，$\text{mex}(\{4, 1, 4, 12, 0, 7, 0, 0, 5\}) = 2$。

Mike 将把牌堆中的所有卡牌分配到若干个非空牌堆中。每张卡牌必须恰好属于一个牌堆。然后，他会计算每个牌堆中卡牌数值的 mex，并将这些 mex 值相加。Mike 希望找到一种分配方式，使得这个总和最大。

此外，牌堆还会经历 $q$ 次修改：有时会向牌堆中添加一张新卡牌，有时会从牌堆中移除一张卡牌。Mike 希望在序列中的每个时刻——即第一次修改前，以及第 $i$ 次修改后（对于每个 $i = 1, 2, \dots, q$）——都能找到使 mex 总和最大的分配方式。

输入格式

第一行包含一个整数 $n$ —— 卡牌数值的范围 ($1 \le n \le 2 \cdot 10^5$)。

第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$ —— 初始时牌堆中数值为 $0, 1, \dots, n-1$ 的卡牌数量 ($0 \le a_i \le 10^6$)。

第三行包含一个整数 $q$ —— 牌堆修改的次数 ($0 \le q \le 2 \cdot 10^5$)。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $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$ 的卡牌。

保证如果 $p_i = 2$，则在第 $i$ 次修改之前，牌堆中至少有一张数值为 $v_i$ 的卡牌。

输出格式

输出 $q + 1$ 个整数 —— 分别表示在经过 $0, 1, \dots, q$ 次修改后，将所有卡牌分配到牌堆中能得到的最大 mex 总和。

样例

样例输入 1

5
2 1 3 0 2
6
1 0
1 1
2 4
1 3
2 1
2 1

样例输出 1

4
5
7
7
9
7
3

说明

对于示例测试的初始牌堆，一种最优的分配方式是将数值为 $0$ 和 $2$ 的卡牌放入一个牌堆，将数值为 $0, 1, 2, 2, 4$ 的卡牌放入另一个牌堆，将数值为 $4$ 的卡牌放入第三个牌堆。该分配方式下的 mex 总和为 $\text{mex}(\{0, 2\}) + \text{mex}(\{0, 1, 2, 2, 4\}) + \text{mex}(\{4\}) = 1 + 3 + 0 = 4$。