시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (언어별 추가 시간 없음) 1024 MB 69 29 27 75.000%

문제

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

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

  1. a1, …, ar을 모두 1씩 감소시킨다.

  2. 이들 중 ai=0이 되는 ai가 하나라도 존재하면, 해당하는 ai들을 모두 수열에서 제거하고, 제거된 원소만큼 “죽은 하수인 수” 카운트를 증가시키고, 다시 1번으로 간다. 그러한 ai가 하나도 없다면, 이 과정을 중단한다.

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

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

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

각 변화가 발생한 후에, “모독” 카드를 한 번 사용한다면 죽게 되는 하수인 수를 구하라. 모든 변화는 누적되며, 실제로 “모독” 카드를 사용하지 않고 이를 쓴 후의 상황을 가정하는 것일 뿐임에 유의하라.

입력

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

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

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

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

T=2가 주어질 때, 전장에 생명력이 K인 하수인이 존재함이 보장된다.

출력

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

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

예제 입력 1

10
1 1
1 2
1 3
1 4
2 2
1 3
1 2
1 5
2 1
1 1

예제 출력 1

1
2
3
4
1
1
5
6
0
6

입력으로 주어진 10가지 변화가 순서대로 발생하는 동안 전장에 있는 하수인의 목록은 다음과 같다. "모독" 카드를 사용하면 죽게 되는 하수인들은 굵은 글씨로 적혀 있다.

[1] / [1 2] / [1 2 3] / [1 2 3 4] / [1 3 4] / [1 3 3 4] / [1 2 3 3 4] / [1 2 3 3 4 5] / [2 3 3 4 5] / [1 2 3 3 4 5]

출처

Contest > 웰노운컵 > 제2회 웰노운컵 Day 1 H번