한빛미디어 (Hard)

시간 제한1초메모리 제한1024 MB

요약

책 가격을 추가하고 삭제하는 쿼리가 주어질 때, 한 페이지의 최대 가격이 최소 가격의 2배 미만이 되도록 책을 나누는 최소 페이지 수를 구합니다.

난이도: 보통10점 중 7점
유형: 그리디, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

한빛미디어(주)는 '책으로 여는 IT 세상'을 만들어 갑니다. IT 세상의 주역은 '우리' 입니다. 한빛미디어(주)는 IT 세상의 주역들을 위한 프로그래밍, 컴퓨터공학, IT 에세이, Make, 리얼타임(전자책), OA, 그래픽, 나와 내 아이를 위한 실용 등 다양한 분야의 책으로 IT 세상을 만들어 가고 있습니다.

대학원을 졸업한 산지니는 2022년부터 부산대학교 프로그래밍 대회의 후원사를 맡아온 한빛미디어로부터 의뢰를 받았다. 한빛미디어가 출판한 책들의 데이터베이스를 이용하는 웹사이트에서 책을 진열하는 프로그램을 개발해 달라는 의뢰였다. 산지니는 기쁜 마음으로 의뢰를 승낙하고 프로그램 개발을 시작했다. 데이터베이스의 책들은 아래 규칙에 따라 웹사이트의 페이지에 진열된다.

웹사이트의 한 페이지에 책을 한 종류 이상 진열해야 한다.
가격이 두 배 이상 차이 나는 책은 한 페이지에 함께 진열할 수 없다. 예를 들어 가격이 $3\,000$ 원인 책은 $5\,000$ 원인 책과 함께 진열할 수 있지만, $6\,000$ 원인 책과는 함께 진열할 수 없다.

산지니는 책이 진열된 페이지가 많으면 고객이 책을 찾기 힘들 것이라고 생각해, 책이 진열될 페이지 수를 최소화하기로 했다. 한빛미디어는 다양한 책을 취급하므로 신간이 추가되기도 하고, 절판되어 더 이상 판매하지 않는 책도 생긴다. 산지니는 이 프로그램을 어떻게 구현해야 할지 고민하고 있다. 산지니를 도와 필요한 페이지 수를 구해 보자.

산지니는 아래 질의를 $Q$ 개 처리하는 프로그램을 작성해야 한다. 질의를 처리하기 전 데이터베이스는 비어 있다.

$1$ $S$ : 가격이 $S$ 인 책을 하나 추가한다.
$2$ $S$ : 가격이 $S$ 인 책을 하나 제거한다. 가격이 $S$ 인 책이 없다면 아무 일도 일어나지 않는다.
$3$ : 모든 책을 진열하기 위해 필요한 페이지 수의 최솟값을 출력한다. 진열할 책이 없다면 $0$ 개의 페이지로 모든 책을 진열할 수 있다.

입력

첫 번째 줄에 질의의 개수를 나타내는 정수 $Q$ 가 주어진다. $(2 \leq Q \leq 2 \times 10^{5})$

두 번째 줄부터 $Q + 1$ 번째 줄까지 한 줄에 하나씩 질의가 주어진다. 질의로 들어오는 책의 가격 $S$ 의 범위는 $10^3$ 이상 $10^6$ 이하이다.

3번 질의는 한 번 이상 주어진다.

출력

3번 질의가 들어올 때마다 필요한 페이지 수의 최솟값을 한 줄에 하나씩 출력한다.

힌트

입출력의 양이 많으므로 빠른 입출력을 사용하는 것을 권장합니다. 언어별 빠른 입출력 방법은 아래와 같습니다.

C++: cin, cout을 사용하는 경우 입출력 전에 cin.tie(nullptr); ios::sync_with_stdio(false);를 한 번 적용해야 합니다. 줄 바꿈할 때는 endl 대신 '\n'을 사용해야 합니다.
Java: BufferedReader와 BufferedWriter를 사용해야 합니다.
Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해야 합니다.

예제3

예제 1
입력
```
3
1 1000
1 2000
3
```
예상 출력
```
2
```

예제 2

입력

예상 출력

1
0
2

예제 3
입력
```
2
1 1000
3
```
예상 출력
```
1
```