تمت ترقية القزم حارس الحديقة مؤخراً ليصبح رئيس جناح الثعالب في حديقة حيوان فروتسواف. حبه للثعلب (أو 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$ مرة أخرى.