Белка Лисска любит орехи. Лисска просит вас посадить ореховые деревья.
Есть n мест (пронумерованных от 1 до n с запада на восток), где можно посадить дерево вдоль улицы. Деревья вырастают на один метр за месяц. В начале каждого месяца вы должны обрабатывать один запрос. Запрос может быть одного из следующих двух типов:
- Посадить дерево высотой h в месте с номером p.
- Срубить x-ое существующее (не срубленное) дерево с запада (где x в 1-индексации). Когда мы срубаем дерево, оно падает вниз и занимает все доступное пространство на месте, где оно стояло. Таким образом, ни одно дерево в этом месте больше посадить нельзя.
После обработки каждого запроса, вы должны вывести длину самой длинной возрастающей подпоследовательности. Подмножество существующих деревьев называется возрастающей подпоследовательностью, если высоты деревьев в нем строго возрастают с запада на восток (например, самое западное дерево в наборе должно иметь самую маленькую высоту). Длина возрастающей подпоследовательности — это количество деревьев в ней.
Обратите внимание, что Лисске не нравятся деревья одинаковой высоты, поэтому гарантируется, что в любой момент времени нет двух деревьев одинаковой высоты.
Выходные данные
Выведите m целых чисел — длину самой длинной возрастающей подпоследовательности после каждого запроса. Разделяйте числа пробельными символами.
Примечание
Вы можете видеть состояние улицы после каждого запроса на следующей анимации:
Если Ваш браузер не поддерживает анимацию png, посмотрите версию в gif здесь: http://212.193.37.254/codeforces/images/162/roadtree.gif
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 6
1 1 1
1 4 4
1 3 4
2 2
1 2 8
2 3
|
1
2
3
2
2
2
|