E. Деревья у дороги
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Белка Лисска любит орехи. Лисска просит вас посадить ореховые деревья.

Есть n мест (пронумерованных от 1 до n с запада на восток), где можно посадить дерево вдоль улицы. Деревья вырастают на один метр за месяц. В начале каждого месяца вы должны обрабатывать один запрос. Запрос может быть одного из следующих двух типов:

  1. Посадить дерево высотой h в месте с номером p.
  2. Срубить x-ое существующее (не срубленное) дерево с запада (где x в 1-индексации). Когда мы срубаем дерево, оно падает вниз и занимает все доступное пространство на месте, где оно стояло. Таким образом, ни одно дерево в этом месте больше посадить нельзя.

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

Обратите внимание, что Лисске не нравятся деревья одинаковой высоты, поэтому гарантируется, что в любой момент времени нет двух деревьев одинаковой высоты.

Входные данные

В первой строке записаны два целых числа: n и m (1  ≤ n ≤ 105; 1 ≤ m ≤ 2·105) — количество мест для деревьев и количество запросов.

В следующих m строках записана информация о запросах в следующем формате:

  • Если тип i-ого запроса — 1, то i-ая строка содержит три целых числа: 1, pi, и hi (1 ≤ pi ≤ n, 1 ≤ hi ≤ 10), где pi — место нового дерева, а hi — изначальная высота нового дерева.
  • Если тип i-ого запроса — 2, то i-ая строка содержит два целых числа: 2 и xi (1 ≤ xi ≤ 10), где xi — это номер дерева, которое мы хотим срубить.

Гарантируется, что входные данные корректны, то есть:

  • Для запросов 1 типа pi будут попарно различны.
  • Для запросов 2 типа xi не будут превышать текущего количества деревьев.
  • В любой момент времени никакие два дерева не имеют одинаковые высоты.

В каждой строке целые числа разделены одиночными пробелами.

Выходные данные

Выведите m целых чисел — длину самой длинной возрастающей подпоследовательности после каждого запроса. Разделяйте числа пробельными символами.

Примеры
Входные данные
4 6
1 1 1
1 4 4
1 3 4
2 2
1 2 8
2 3
Выходные данные
1
2
3
2
2
2
Примечание

Вы можете видеть состояние улицы после каждого запроса на следующей анимации:

Если Ваш браузер не поддерживает анимацию png, посмотрите версию в gif здесь: http://212.193.37.254/codeforces/images/162/roadtree.gif