시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB209836953.906%

문제

준원이가 좋아하는 하스스톤의 주문 카드 “모독”은 다음과 같은 효과를 지닌다: “모든 하수인에게 피해를 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 또는 T = 2, 1 ≤ K ≤ 1,000,000)

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

T = 2일 때에는, 생명력이 K인 하수인 하나가 전장에서 제거된다. 전장에 생명력이 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 2 3 4
  5. 1 3 4
  6. 1 3 3 4
  7. 1 2 3 3 4
  8. 1 2 3 3 4 5
  9. 2 3 3 4 5
  10. 1 2 3 3 4 5

출처

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