Хайуанаттар бағының қызметкері Ергежейлі жақында Вроцлав хайуанаттар бағындағы Түлкілер павильонының басшысы қызметіне көтерілді. Оның түлкіге (немесе поляк тілінде аталатындай lis-ке) деген сүйіспеншілігінде шек жоқ.

Ергежейлі негізгі жолдың бойында орналасқан қоршаулардағы түлкілердің ұзын қатарына күтім жасайды. Әр түлкінің көркемдік (magnificence) мәні бар, ал ергежейлі өз түлкілерінің арасынан көркемдіктің ең ұзын өспелі ішкі тізбегін (LIS) табуды мақтан тұтады.

Бүгін ергежейлі кейбір түлкілерді басқа хайуанаттар бақтарына ауыстырып, оларды басқа хайуанаттар бақтары орнына жіберген түлкілермен алмастыруда. Күннің басында Хайуанаттар бағының қызметкері Ергежейлі жаңа түлкілер салынған арбамен бірінші (ең сол жақтағы) қоршаудың жанында тұрады. Ергежейлі жол бойымен жүріп, қоршаудан қоршауға өтеді. Кейде ол қоршаулардың бірінде тоқтап, ондағы түлкіні көркемдігі басқа болуы мүмкін басқа түлкімен алмастырады. Бұл орын алған сайын, ол дереу ең ұзын өспелі көркемдік ішкі тізбегінің ұзындығын есептеуі керек. Оған осы санды бақылап отыруға көмектесе аласыз ба?

Кіріс деректері

Кіріс деректерінің бірінші жолында жол бойындағы қоршаулар санын және ергежейлі жасайтын әрекеттер санын білдіретін екі бүтін сан $N$ және $Q$ берілген.

Кіріс деректерінің екінші жолында әр түлкінің бастапқы көркемдігін сипаттайтын $N$ бүтін сан $m_1, m_2, \dots, m_N$ берілген.

Келесі $Q$ жол әрекеттерді сипаттайды. Бір әрекет келесілердің бірі болып табылады:

1. < — ергежейлі бір қоршауға солға жылжиды,
2. > — ергежейлі бір қоршауға оңға жылжиды,
3. ! v — ергежейлі ағымдағы қоршаудағы түлкіні көркемдігі $v$ болатын түлкіге ауыстырады.

Шығыс деректері

Әрбір ! әрекеті үшін түлкілер көркемдігінің ең ұзын өспелі ішкі тізбегінің ұзындығы бар бір жолды шығарыңыз.

Шектеулер

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

Мысалдар

Кіріс 1

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

Шығыс 1

2
3
2

Ескертпе

Алдымен Хайуанаттар бағының қызметкері Ергежейлі екінші қоршауға өтіп, түлкіні көркемдігі $2$ болатын түлкіге ауыстырады. Ең ұзын өспелі ішкі тізбектің ұзындығы $2$-ге тең. Содан кейін ол бесінші қоршауға өтіп, түлкіні көркемдігі $10$ болатын түлкіге ауыстырады, сонда LIS ұзындығы $3$ болады. Соңында қызметкер төртінші қоршауға өтіп, көркемдікті $11$-ге өзгертеді, нәтижесінде LIS ұзындығы қайтадан $2$ болады.