Гном-Доглядач зоопарку нещодавно був підвищений до голови Павільйону лисиць у Вроцлавському зоопарку. Його любов до лисиці (або 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$.