Задача D. Детский утренник

Автор:Артем Завгороднев   Ограничение времени:3 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

В некоторой школе для одаренных детей у ребят появился новый тренд - вставать в ряд по неубыванию роста, т.е так, чтобы рост следующего школьника в ряду был не меньше роста текущего. Однако быть самым низким не нравится никому, поэтому каждый из школьников говорит вам, что он не хочет стоять в последних ai местах (некоторые школьники не капризные вовсе и могут стоять на последнем месте).

Всего есть n школьников, которые приходят в ряд по очереди. Вам требуется после каждого нового школьника сказать, ряд какой максимальной длины можно составить из них.

Формат входных данных

В первой строке входных данных находится целое число n. (1 ≤ n ≤ 105)

В следующих n строках располагается пара из вещественного и целого чисел hi и ai - рост школьника в сантиметрах и количество последних мест, на которые он не будет вставать. Рост имеет 6 знаков после точки. (130 ≤ hi ≤ 190, 0 ≤ ai < n)

Формат выходных данных

Вам требуется вывести n целых чисел: в i-ой строке максимальную длину ряда, который можно составить из первых i школьников. (1 ≤ i ≤ n)

Примеры тестов

Стандартный вход Стандартный выход
1
5
174.500000 0
175.000000 1
173.000000 1
171.000000 0
180.000000 5
1
2
2
4
4
2
5
150.000000 1
150.000000 2
150.000000 0
150.000000 3
150.000000 4
0
0
3
4
5

0.087s 0.009s 13