Dvergen Dyrepasseren har nylig blitt forfremmet til leder for Revepaviljongen i Wrocław Zoo. Hans kjærlighet til reven (eller lis, som den kalles på polsk) kjenner ingen grenser.

Dvergen passer på en lang rekke med rever i innhegninger som ligger langs hovedstien. Hver rev har en praktverdi (magnificence), og dvergen er stolt av å finne den lengste stigende delsekvensen (LIS) av prakt blant revene sine.

I dag overfører dvergen noen rever til andre dyrehager og erstatter dem med rever som de andre dyrehagene har sendt i retur. På begynnelsen av dagen står Dvergen Dyrepasseren med en vogn med nye rever ved siden av den første innhegningen (lengst til venstre). Dvergen vil gå langs stien og bevege seg fra innhegning til innhegning. Noen ganger vil han stoppe ved en av innhegningene og bytte ut reven der med en annen rev, muligens med en annen prakt. Hver gang dette skjer, må han umiddelbart beregne lengden på den lengste stigende delsekvensen av prakt. Kan du hjelpe ham med å holde oversikt over dette tallet?

Inndata

Den første linjen i inndataene inneholder to heltall $N$ og $Q$, som representerer antallet innhegninger langs stien og antallet handlinger dvergen utfører.

Den andre linjen i inndataene inneholder $N$ heltall $m_1, m_2, \dots, m_N$, som beskriver den opprinnelige prakten til hver rev.

De neste $Q$ linjene beskriver handlingene. En enkelt handling er en av følgende:

1. < — dvergen flytter seg én innhegning til venstre,
2. > — dvergen flytter seg én innhegning til høyre,
3. ! v — dvergen bytter ut reven i den nåværende innhegningen med en rev med prakt $v$.

Utdata

For hver !-handling skal du skrive ut én enkelt linje som inneholder lengden på den lengste stigende delsekvensen av revenes prakt.

Begrensninger

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

Eksempler

Inndata 1

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

Utdata 1

2
3
2

Forklaring

Først flytter Dvergen Dyrepasseren seg til den andre innhegningen og bytter ut reven med en som har prakt $2$. Lengden på den lengste stigende delsekvensen er $2$. Deretter flytter han seg til den femte innhegningen og bytter ut reven med en som har prakt $10$, og lengden på LIS blir $3$. Til slutt flytter Dyrepasseren seg til den fjerde innhegningen og endrer prakten til $11$, slik at lengden på LIS blir $2$ igjen.