드문 곤충

블랑콘씨의 집 주위를 돌아다니는 $N$ 마리의 곤충이 있고, 각각 $0$에서 $N - 1$로 번호가 매겨져 있다. 각 곤충마다 자신이 속하는 종류가 있고, $0$ 이상 $10^9$ 이하인 정수로 표현된다. 복수의 곤충이 같은 종류에 속할 수 있다.

곤충들을 종류에 따라 그룹으로 모아보기로 하자. 가장 자주 나오는 곤충 종류 그룹의 크기는 가장 많은 수의 곤충이 속하는 그룹의 곤충 수이다. 비슷하게, 가장 드문 곤충 종류 그룹의 크기는 가장 적은 수의 곤충이 속하는 그룹의 곤충 수이다.

예를 들어, $11$ 마리의 곤충이 있고, 종류가 차례로 $\[5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]$라고 하자. 이 경우, 가장 자주 나오는 곤충 종류 그룹의 크기는 $3$이다. 종류 $9$인 곤충의 그룹과 종류 $11$인 곤충의 그룹이 가장 자주 나오는 곤충 종류 그룹이며, 각각 $3$ 마리의 곤충으로 이루어져 있다. 가장 드문 곤충 종류 그룹의 크기는 $1$이다. 종류 $7$, 종류 $0$, 종류 $100$인 곤충의 그룹에는 각각 $1$ 마리의 곤충이 속한다.

블랑콘씨는 곤충의 종류를 알지 못한다. 곤충의 종류에 대한 정보를 알려주는 단추가 하나 달린 기계가 있다. 처음, 이 기계는 비어 있다. 기계를 이용하기 위해, 다음 세 가지 종류의 연산을 사용할 수 있다.

1. 곤충 한 마리를 기계 안에 넣는다.
2. 곤충 한 마리를 기계에서 빼낸다.
3. 기계의 단추를 누른다.

각각의 연산은 최대 $40\\,000$ 번 수행될 수 있다.

단추가 눌려질 때마다, 이 기계는 현재 기계에 들어 있는 곤충들만 이용해서, 이 중 가장 자주 나오는 곤충 종류 그룹의 크기를 알려준다.

당신이 할 일은 이 기계를 사용해서 블랑콘씨 집 주위의 $N$ 마리 곤충들 중 가장 드문 곤충 종류 그룹의 크기를 구하는 것이다. 덤으로, 어떤 서브태스크에서는, 특정한 명령이 실행되는 횟수에 따라 여러분의 점수가 결정된다 (자세한 내용은 Subtasks 참고).

• $2 \le N \le 2000$