34961번 - 급식실 식탁 배정 서브태스크

문제

서울과학고등학교의 급식실은 매 식사시간 밥을 먹으려는 학생들로 붐빈다.

학생들은 밥을 먹기 위해서는 식탁에 앉아야 하는데, 각 학생은 자신이 앉은 식탁에 앉은 사람의 수에 대한 선호도 $X$를 가지고 있다. 선호도 $X$를 가진 학생은 본인을 포함하여 $X$명 이하의 학생이 있는 식탁에서만 밥을 먹으려고 한다. 즉, $N$명이 앉아 있는 식탁의 모든 학생은 선호도가 $N$ 이상이어야 한다.

여러분은 각 학생의 선호도를 존중하면서 모든 학생을 최소 개수의 식탁에 배정하려고 한다. 급식실의 상태는 비어 있는 상태로 시작하며, 매 출입마다 한 명이 들어오거나 나간다. 급식실에 사람들이 출입하면서 각 출입 이후 모든 학생을 식탁에 배정하기 위한 최소 식탁의 개수를 계산하라.

입력

첫째 줄에 들어오고 나가는 사람의 수 $Q$가 주어진다.

둘째 줄부터 $Q$개의 줄에 걸쳐 $i+1$번째 줄에 $i$번째로 출입하는 사람의 정보를 나타내는 정수 $T,ドル $X$가 공백으로 구분되어 주어진다.

$T$가 1ドル$이면 선호도 $X$의 사람이 급식실에 들어왔음을, $T$가 2ドル$인 경우 선호도 $X$인 사람 한 명이 급식실에서 나갔음을 의미한다.

첫 시점에서 $T$는 1ドル$임이 보장되고, $T$가 2ドル$인 경우 현재 급식실에 선호도 $X$인 사람이 존재함이 보장된다.

출력

첫째 줄부터 $Q$개의 줄에 걸쳐 정답을 출력한다. $i$번째 줄에는 $i$번째 출입 후 급식실의 사람들을 식탁에 배정하기 위한 최소 식탁의 수를 출력한다.

제한

• 1ドル\le Q\le 200,円 000$
• $T\in\{1,2\},ドル 1ドル\le X\le 200,円 000$

서브태스크

노트