31792번 - 한빛미디어 (Hard)

이 문제는 "한빛미디어(Easy)" 문제와 입력 조건과 출력 조건이 다르다.

한빛미디어(주)는 '책으로 여는 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()을 사용해야 합니다.