시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 38 14 5 83.333%

문제

디디는 1 X 4 'ㅡ'자, 4 X 1 'ㅣ'자 모양 블럭으로만 진행되는 테트리스를 하고 있다. 이 테트리스는 어떤 블럭의 떨어질 위치를 정하면 그 위치에서 수직방향으로 떨어지며, 수평방향으로 움직이거나 블럭을 회전시킬 수 없다. 또한 떨어지는 블럭의 아랫면이, 다른 블럭의 윗면 혹은 바닥과 1칸이라도 맞닿는다면, 이 블럭은 떨어지는 것을 멈추고 맞닿는 면 위에 쌓이게 된다.

'이 블럭이 떨어지면 그 밑에 있는 블럭들은 많이 아프겠ㄷr...' 테트리스를 감성으로 하는 디디는 어떤 블럭이 떨어질 때 하중을 받는 블럭의 개수를 구하려고 한다. 떨어지는 블럭의 아랫면과 면을 공유하는 블럭은 하중을 받으며, 하중을 받은 블럭들의 아랫면과 면을 공유하는 블럭들 또한 하중을 받게 된다.

<빨간색 블럭은 이번에 떨어뜨린 블럭이며, 노란색 블럭은 이때 하중을 받는 블럭이다.>

착한 leejseo는 감성이 풍부한 디디를 위해, 디디가 블럭을 떨어뜨릴 때마다 그 블럭의 하중을 받는 블럭의 개수를 구하는 프로그램을 작성하려고 한다. leejseo를 따라서 디디를 도와주자.

입력

첫째 줄에 디디가 떨어뜨린 블럭의 개수 Q(1 ≤ Q ≤ 105)가 주어진다.
둘째 줄부터 Q개의 각 줄에는 디디가 떨어뜨린 블럭에 대한 정보가 주어진다.
각 줄은 아래 2개 중 하나의 형식을 가지고 있다.

  • 1 a : 블럭의 왼쪽 끝 칸이 위치 a에 위치하게 'ㅡ'자 모양의 블럭을 떨어뜨린다.
  • 2 a : 위치 a에 'ㅣ'자 모양의 블럭을 떨어뜨린다.

단, a는 항상 정수이며 블럭의 어떤 부분도 위치 1 ~ 400,000를 벗어나지 않는다.

출력

Q개의 각 줄에 디디가 블럭을 떨어뜨릴 때마다 그 블럭의 하중을 받는 블럭의 개수를 출력하라.

서브태스크 1 (34점)

떨어뜨린 블럭의 개수는 1000을 넘지 않는다.

서브태스크 2 (66점)

떨어뜨린 블럭은 전부 'ㅡ'자 모양이다.

서브태스크 3 (50점)

추가적인 제약 조건이 없다.

예제 입력 1

6
1 5
2 5
2 6
2 7
2 8
1 5

예제 출력 1

0
1
1
1
1
5

예제 입력 2

9
1 5
1 9
1 6
1 5
1 7
1 11
1 11
1 11
1 9

예제 출력 2

0
0
2
3
4
1
2
3
8

채점

  • 예제는 채점하지 않는다.