คนแคระผู้ดูแลสวนสัตว์เพิ่งได้รับการเลื่อนตำแหน่งเป็นหัวหน้าศาลาสุนัขจิ้งจอกที่สวนสัตว์วรอตสวัฟ ความรักที่เขามีต่อสุนัขจิ้งจอก (หรือที่ในภาษาโปแลนด์เรียกว่า lis) นั้นไร้พรมแดน
คนแคระดูแลแถวยาวของสุนัขจิ้งจอกในกรงที่เรียงรายอยู่ตามทางเดินหลัก สุนัขจิ้งจอกแต่ละตัวมีค่า ความสง่างาม และคนแคระก็ภูมิใจในการหา ลำดับย่อยเพิ่มขึ้นที่ยาวที่สุด (LIS) ของความสง่างามในหมู่สุนัขจิ้งจอกของเขา
วันนี้ คนแคระกำลังย้ายสุนัขจิ้งจอกบางตัวไปยังสวนสัตว์อื่น และแทนที่พวกมันด้วยสุนัขจิ้งจอกที่สวนสัตว์อื่นส่งกลับมาให้ ในตอนเริ่มต้นของวัน คนแคระผู้ดูแลสวนสัตว์ยืนอยู่พร้อมกับรถเข็นที่มีสุนัขจิ้งจอกตัวใหม่ๆ ข้างกรงแรก (ซ้ายสุด) คนแคระจะเดินไปตามทางเดิน โดยเคลื่อนที่จากกรงหนึ่งไปยังอีกกรงหนึ่ง บางครั้งเขาจะหยุดที่กรงใดกรงหนึ่งและเปลี่ยนสุนัขจิ้งจอกที่นั่นเป็นสุนัขจิ้งจอกอีกตัวหนึ่ง ซึ่งอาจมีความสง่างามแตกต่างไปจากเดิม ทุกครั้งที่เกิดเหตุการณ์นี้ขึ้น เขาจะต้องคำนวณความยาวของลำดับย่อยความสง่างามที่เพิ่มขึ้นที่ยาวที่สุดทันที คุณสามารถช่วยเขาติดตามตัวเลขนี้ได้หรือไม่?
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มสองตัวคือ $N$ และ $Q$ แทนจำนวนกรงตามทางเดินและจำนวนการกระทำที่คนแคระทำ
บรรทัดที่สองของข้อมูลนำเข้ามีจำนวนเต็ม $N$ ตัว คือ $m_1, m_2, \dots, m_N$ อธิบายความสง่างามเริ่มต้นของสุนัขจิ้งจอกแต่ละตัว
อีก $Q$ บรรทัดถัดไปอธิบายการกระทำ การกระทำแต่ละครั้งเป็นหนึ่งในรูปแบบต่อไปนี้:
<— คนแคระเคลื่อนที่ไปทางซ้ายหนึ่งกรง>— คนแคระเคลื่อนที่ไปทางขวาหนึ่งกรง! 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$ อีกครั้ง