Mex와 카드

Mike는 카드를 가지고 노는 것을 좋아한다. 그의 덱에 있는 각 카드에는 0부터 n-1까지의 정수 하나가 적혀 있다. 처음에 덱에는 값이 i인 카드가 $a_i$장 있다.

Mike는 오늘 mex 개념을 배우고 있다. 정수 집합의 mex는 집합에 속하지 않는 가장 작은 0 이상의 정수이다. 예를 들어 $\operatorname{mex}(\{4, 1, 4, 12, 0, 7, 0, 0, 5\}) = 2$이다.

Mike는 덱의 모든 카드를 비어 있지 않은 더미들로 나눈다. 각 카드는 정확히 한 더미에 속한다. 그다음 각 더미에 있는 카드 값의 mex를 구해 모두 더한다. Mike는 이 합이 최대가 되는 분배를 찾고 싶어 한다.

덱에는 q번의 수정이 일어난다. 카드가 추가되기도 하고 제거되기도 한다. Mike는 첫 번째 수정 전과, 각 i = 1, 2, \ldots, q에 대해 처음 i번의 수정 후에 mex 합이 최대가 되는 분배를 구하고 싶어 한다.

첫 줄에는 카드 값의 범위 n이 주어진다 ($1 \le n \le 2 \cdot 10^5$).

둘째 줄에는 n개의 정수 $a_0, a_1, \ldots, a_{n-1}$이 주어진다. 이는 처음 덱에 있는 값 0, 1, \ldots, n-1 카드의 개수이다 ($0 \le a_i \le 10^6$).

셋째 줄에는 덱 수정 횟수 q가 주어진다 ($0 \le q \le 2 \cdot 10^5$).

다음 q개의 줄 중 i번째 줄에는 i번째 수정을 나타내는 두 정수 $p_i$와 $v_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$개의 정수를 출력한다. j번째 정수는 덱의 처음 j-1번 수정 후에, 모든 카드를 비어 있지 않은 더미로 나누는 유효한 분배들 중 mex 합의 최댓값이다 ($j = 1, 2, \ldots, q+1$).

예제 테스트에서 처음 덱에 대한 최적 분배 중 하나는 값 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$이다.