הגמד שומר גן החיות קודם לאחרונה לתפקיד ראש ביתן השועלים בגן החיות של ורוצלב. אהבתו לשועל (או 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$ שוב.