Dýragarðsvörðurinn Dvergur hefur nýlega veriðหækkaður í tign og gerður að yfirmanni Refaskálans í Dýragarðinum í Wrocław. Ást hans á refnum (eða lis, eins og hann er kallaður á pólsku) á sér engin takmörk.

Dvergurinn hugsar um langa röð af refum í girðingum sem raðað er meðfram aðalgöngustígnum. Hver refur hefur glæsileikagildi (magnificence), og dvergurinn leggur metnað sinn í að finna lengstu vaxandi hlutrunu (LIS) glæsileika meðal refanna sinna.

Í dag er dvergurinn að flytja nokkra refi í aðra dýragarða og skipta þeim út fyrir refi sem hinir dýragarðarnir sendu í staðinn. Í upphafi dags stendur Dýragarðsvörðurinn Dvergur með kerru af nýjum refum við hliðina á fyrstu girðingunni (lengst til vinstri). Dvergurinn mun ganga meðfram stígnum og færa sig úr einni girðingu í aðra. Stundum mun hann stoppa við eina girðinguna og skipta refnum þar út fyrir annan ref, mögulega með annan glæsileika. Í hvert sinn sem þetta gerist verður hann samstundis að reikna út lengd lengstu vaxandi hlutrunu glæsileika. Geturðu hjálpað honum að halda utan um þessa tölu?

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $N$ og $Q$, sem tákna fjölda girðinga meðfram stígnum og fjölda aðgerða sem dvergurinn framkvæmir.

Önnur lína inntaksins inniheldur $N$ heiltölur $m_1, m_2, \dots, m_N$, sem lýsa upphaflegum glæsileika hvers refs.

Næstu $Q$ línur lýsa aðgerðunum. Ein aðgerð er eitt af eftirfarandi:

1. < — dvergurinn færir sig um eina girðingu til vinstri,
2. > — dvergurinn færir sig um eina girðingu til hægri,
3. ! v — dvergurinn skiptir refnum í núverandi girðingu út fyrir ref með glæsileika $v$.

Úttak

Fyrir hverja ! aðgerð skaltu prenta eina línu sem inniheldur lengd lengstu vaxandi hlutrunu glæsileika refanna.

Takmarkanir

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

Dæmi

Inntak 1

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

Úttak 1

2
3
2

Athugasemd

Fyrst færir Dýragarðsvörðurinn Dvergur sig í aðra girðinguna og skiptir refnum út fyrir ref með glæsileika $2$. Lengd lengstu vaxandi hlutrununnar er $2$. Síðan færir hann sig í fimmtu girðinguna og skiptir refnum út fyrir ref með glæsileika $10$, og lengd LIS verður $3$. Að lokum færir Dýragarðsvörðurinn sig í fjórðu girðinguna og breytir glæsileikanum í $11$, sem gerir lengd LIS aftur að $2$.