16221번 - 모독

준원이가 좋아하는 하스스톤의 주문 카드 “모독”은 다음과 같은 효과를 지닌다: “모든 하수인에게 피해를 1 줍니다. 하나라도 죽으면, 이 주문을 다시 시전합니다.”

다른 말로 설명하면 다음과 같다. 현재 전장에 있는 하수인들의 생명력들을 길이 r인 양의 정수열 a₁, …, a_r로 나타내자. “모독” 카드를 쓰면 수열 a에 아래와 같은 연산을 하게 된다.

1. a₁, …, a_r을 모두 1씩 감소시킨다.
2. a_i = 0이 되는 수열의 원소 a_i가 하나라도 존재한다면, 해당하는 a_i들을 모두 수열에서 제거하고, 다시 1.로 돌아간다. 제거된 원소의 개수만큼 “죽은 하수인 수” 카운트를 증가시킨다. 그러한 a_i가 하나도 없다면, 과정을 중단한다.

현재 전장에는 하수인이 하나도 없다. 하스스톤에는 수많은 변수가 있지만, 다음 두 가지의 변화만이 발생한다고 가정하자.

1. 생명력이 k인 하수인 하나가 전장에 추가된다.
2. 생명력인 k인 하수인 하나가 전장에서 제거된다.

각 변화가 발생한 후에, 당신은 “모독” 카드를 한 번 사용했을 때에 죽는 하수인 수를 구해야 한다.

모든 변화는 누적된다. 또한, 실제로 “모독” 카드를 사용하지 않고 카드를 사용했을 때의 상황을 가정하는 것일 뿐임에 유의하라.

첫 줄에는 전장에 발생하는 변화의 수인 Q가 주어진다. (1 ≤ Q ≤ 1,000,000)

그 뒤 Q개의 줄에는 전장에 발생하는 각 변화를 나타내는 두 개의 정수 T, K가 주어진다. (T = 1 또는 T = 2, 1 ≤ K ≤ 1,000,000)

T = 1일 때에는, 생명력이 K인 하수인 하나가 전장에 추가된다.

T = 2일 때에는, 생명력이 K인 하수인 하나가 전장에서 제거된다. 전장에 생명력이 K인 하수인이 이 때 하나 이상 존재함이 보장된다.

입력에 주어진 각 변화가 발생한 뒤, “모독” 카드를 사용한다면 죽게 되는 하수인의 수를 구하여, 한 줄에 하나씩 출력한다.

입출력의 크기가 매우 크므로, 빠른 입출력 방식을 사용하는 것을 권장한다.