Гном-Смотритель зоопарка недавно был повышен до главы Павильона лис во Вроцлавском зоопарке. Его любовь к лисе (или lis, как ее называют по-польски) не знает границ.
Гном ухаживает за длинным рядом лис в вольерах, расположенных вдоль главной аллеи. У каждой лисы есть показатель великолепия, и гном гордится тем, что находит наибольшую возрастающую подпоследовательность (LIS — Longest Increasing Subsequence) великолепия среди своих лис.
Сегодня гном передает некоторых лис в другие зоопарки и заменяет их лисами, которых другие зоопарки прислали взамен. В начале дня Гном-Смотритель стоит с тележкой новых лис рядом с первым (самым левым) вольером. Гном будет идти вдоль аллеи, переходя от вольера к вольеру. Иногда он будет останавливаться у одного из вольеров и заменять находящуюся там лису на другую, возможно, с другим великолепием. Каждый раз, когда это происходит, он должен немедленно вычислить длину наибольшей возрастающей подпоследовательности великолепия. Сможете ли вы помочь ему следить за этим числом?
Входные данные
Первая строка входных данных содержит два целых числа $N$ и $Q$, обозначающих количество вольеров вдоль аллеи и количество действий, которые совершает гном.
Вторая строка входных данных содержит $N$ целых чисел $m_1, m_2, \dots, m_N$, описывающих начальное великолепие каждой лисы.
Следующие $Q$ строк описывают действия. Одно действие имеет один из следующих видов:
<— гном перемещается на один вольер влево,>— гном перемещается на один вольер вправо,! v— гном меняет лису в текущем вольере на лису с великолепием $v$.
Выходные данные
Для каждого действия ! выведите одну строку, содержащую длину наибольшей возрастающей подпоследовательности великолепия лис.
Ограничения
$2 \le N \le 200\,000$, $1 \le Q \le 500\,000$, $1 \le m_i \le 10^6$, $1 \le v \le 10^6$.
Примеры
Входные данные 1
5 8 3 4 1 7 2 > ! 2 > > > ! 10 < ! 11
Выходные данные 1
2 3 2
Примечание
Сначала Гном-Смотритель переходит ко второму вольеру и меняет лису на лису с великолепием $2$. Длина наибольшей возрастающей подпоследовательности равна $2$. Затем он переходит к пятому вольеру и меняет лису на лису с великолепием $10$, и длина LIS становится равной $3$. Наконец, Смотритель переходит к четвертому вольеру и меняет великолепие на $11$, в результате чего длина LIS снова становится равной $2$.