Krasnolud Opiekun Zwierząt został niedawno awansowany na kierownika Pawilonu Lisów we wrocławskim zoo. Jego miłość do lisa (czyli po angielsku fox, skąd skrót LIS!) nie zna granic.
Krasnolud opiekuje się długim rzędem lisów w wybiegach rozmieszczonych wzdłuż głównej alejki. Każdy lis ma pewną wartość wspaniałości, a krasnolud szczyci się znajdowaniem Najdłuższego Podciągu Rosnącego (LIS — Longest Increasing Subsequence) wspaniałości wśród swoich lisów.
Dzisiaj krasnolud przekazuje niektóre lisy do innych ogrodów zoologicznych i zastępuje je lisami, które tamte ogrody przysłały w zamian. Na początku dnia Krasnolud Opiekun Zwierząt stoi z wózkiem nowych lisów obok pierwszego (skrajnie lewego) wybiegu. Krasnolud będzie spacerował wzdłuż alejki, przemieszczając się od wybiegu do wybiegu. Czasami zatrzyma się przy jednym z wybiegów i podmieni znajdującego się tam lisa na innego, być może o innej wspaniałości. Za każdym razem, gdy to nastąpi, musi natychmiast obliczyć długość najdłuższego rosnącego podciągu wspaniałości. Czy pomożesz mu śledzić tę liczbę?
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite $N$ oraz $Q$, oznaczające liczbę wybiegów wzdłuż alejki oraz liczbę akcji wykonywanych przez krasnoluda.
Drugi wiersz wejścia zawiera $N$ liczb całkowitych $m_1, m_2, \dots, m_N$, opisujących początkową wspaniałość każdego lisa.
Kolejne $Q$ wierszy opisuje akcje. Pojedyncza akcja jest jedną z następujących:
<— krasnolud przemieszcza się o jeden wybieg w lewo,>— krasnolud przemieszcza się o jeden wybieg w prawo,! v— krasnolud wymienia lisa w bieżącym wybiegu na lisa o wspaniałości $v$.
Wyjście
Dla każdej akcji ! wypisz jeden wiersz zawierający długość najdłuższego podciągu rosnącego wspaniałości lisów.
Ograniczenia
$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$.
Przykłady
Wejście 1
5 8 3 4 1 7 2 > ! 2 > > > ! 10 < ! 11
Wyjście 1
2 3 2
Uwaga
Najpierw Krasnolud Opiekun Zwierząt przemieszcza się do drugiego wybiegu i wymienia lisa na innego o wspaniałości $2$. Długość najdłuższego podciągu rosnącego wynosi $2$. Następnie przemieszcza się do piątego wybiegu i wymienia lisa na innego o wspaniałości $10$, przez co długość LIS staje się równa $3$. Na koniec Opiekun przemieszcza się do czwartego wybiegu i zmienia wspaniałość na $11$, sprawiając, że długość LIS ponownie wynosi $2$.