Dvärgen Djurskötaren har nyligen befordrats till chef för Rävpaviljongen på Wrocławs zoo. Hans kärlek till räven (eller lis, som den kallas på polska) känner inga gränser.

Dvärgen tar hand om en lång rad av rävar i inhägnader som är placerade längs huvudgången. Varje räv har ett praktvärde (magnificence), och dvärgen är stolt över att hitta den längsta växande delsekvensen (LIS) av prakt bland sina rävar.

Idag flyttar dvärgen några rävar till andra djurparker och ersätter dem med rävar som de andra djurparkerna har skickat i utbyte. I början av dagen står Dvärgen Djurskötaren med en vagn med nya rävar bredvid den första (längst till vänster belägna) inhägnaden. Dvärgen kommer att gå längs gången och förflytta sig från inhägnad till inhägnad. Ibland stannar han vid en av inhägnaderna och byter ut räven där mot en annan räv, eventuellt med en annan prakt. Varje gång detta händer måste han omedelbart beräkna längden på den längsta växande delsekvensen av prakt. Kan du hjälpa honom att hålla reda på detta tal?

Indata

Den första raden i indatan innehåller två heltal $N$ och $Q$, som representerar antalet inhägnader längs gången och antalet handlingar som dvärgen utför.

Den andra raden i indatan innehåller $N$ heltal $m_1, m_2, \dots, m_N$, som beskriver den ursprungliga prakten hos varje räv.

De följande $Q$ raderna beskriver handlingarna. En enskild handling är en av följande:

1. < — dvärgen flyttar sig en inhägnad åt vänster,
2. > — dvärgen flyttar sig en inhägnad åt höger,
3. ! v — dvärgen byter ut räven i den nuvarande inhägnaden mot en räv med prakten $v$.

Utdata

För varje !-handling, skriv ut en enda rad som innehåller längden på den längsta växande delsekvensen av rävarnas prakt.

Begränsningar

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

Exempel

Indata 1

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

Utdata 1

2
3
2

Förklaring

Först flyttar sig Dvärgen Djurskötaren till den andra inhägnaden och byter ut räven mot en med prakten $2$. Längden på den längsta växande delsekvensen är $2$. Sedan flyttar han sig till den femte inhägnaden och byter ut räven mot en med prakten $10$, och längden på LIS blir $3$. Slutligen flyttar sig Djurskötaren till den fjärde inhägnaden och ändrar prakten till $11$, vilket gör att längden på LIS blir $2$ igen.