Eläintenhoitajakääpiö on äskettäin ylennetty Wrocławin eläintarhan Kettupaviljongin johtajaksi. Hänen rakkautensa kettuun (tai lis, kuten sitä puolaksi kutsutaan) ei tunne rajoja.

Kääpiö huolehtii pitkästä rivistä kettuja aitauksissa, jotka on järjestetty pääkäytävän varrelle. Jokaisella ketulla on loistokkuusarvo (magnificence), ja kääpiö on ylpeä voidessaan etsiä kettujensa loistokkuuksien pisimmän aidosti kasvavan alijonon (LIS).

Tänään kääpiö siirtää joitakin kettuja muihin eläintarhoihin ja korvaa ne ketuilla, jotka muut eläintarhat lähettivät vastineeksi. Päivän alussa Eläintenhoitajakääpiö seisoo uusia kettuja sisältävän kärryn kanssa ensimmäisen (vasemmanpuoleisimman) aitauksen vieressä. Kääpiö kävelee käytävää pitkin siirtyen aitauksesta toiseen. Joskus hän pysähtyy jonkin aitauksen kohdalle ja korvaa siellä olevan ketun toisella ketulla, jolla on mahdollisesti eri loistokkuus. Joka kerta kun näin tapahtuu, hänen on välittömästi laskettava pisimmän kasvavan loistokkuusalijonon pituus. Voitko auttaa häntä pitämään kirjaa tästä luvusta?

Syöte

Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $N$ ja $Q$, jotka kuvaavat käytävän varrella olevien aitausten lukumäärää ja kääpiön tekemien toimintojen lukumäärää.

Syötteen toinen rivi sisältää $N$ kokonaislukua $m_1, m_2, \dots, m_N$, jotka kuvaavat kunkin ketun alkuperäisen loistokkuuden.

Seuraavat $Q$ riviä kuvaavat toiminnot. Yksittäinen toiminto on jokin seuraavista:

1. < — kääpiö siirtyy yhden aitauksen vasemmalle,
2. > — kääpiö siirtyy yhden aitauksen oikealle,
3. ! v — kääpiö vaihtaa nykyisessä aitauksessa olevan ketun kettuun, jonka loistokkuus on $v$.

Tuloste

Tulosta jokaista !-toimintoa kohden yksi rivi, joka sisältää kettujen loistokkuuden pisimmän kasvavan alijonon pituuden.

Rajoitukset

$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$.

Esimerkit

Syöte 1

5 8
3 4 1 7 2
>
! 2
>
>
>
! 10
<
! 11

Tuloste 1

2
3
2

Huomautus

Ensin Eläintenhoitajakääpiö siirtyy toiseen aitaukseen ja vaihtaa ketun sellaiseen, jonka loistokkuus on $2$. Pisimmän kasvavan alijonon pituus on $2$. Sitten hän siirtyy viidenteen aitaukseen ja vaihtaa ketun sellaiseen, jonka loistokkuus on $10$, jolloin LIS:n pituudeksi tulee $3$. Lopuksi Eläintenhoitaja siirtyy neljänteen aitaukseen ja muuttaa loistokkuudeksi $11$, jolloin LIS:n pituus on jälleen $2$.