เรานิยาม $\operatorname{mex}(S)$ เป็นจำนวนเต็มไม่ลบที่น้อยที่สุดที่ไม่อยู่ใน $S$
คุณได้รับเพอร์มิวเทชัน $p$ ที่ประกอบด้วยสมาชิก $n$ ตัวตั้งแต่ $0$ ถึง $n - 1$ และคุณยังมีช่วง $[l_i, r_i]$ จำนวน $m$ ช่วง ซึ่งคุณนำมาใช้สร้างกราฟด้วยวิธีต่อไปนี้:
- สำหรับแต่ละคู่ของจุดยอด $i \neq j$ คุณจะเพิ่มเส้นเชื่อมที่มีค่าใช้จ่ายเท่ากับ $\operatorname{mex}$ ของยูเนียนของค่าในเพอร์มิวเทชันบนช่วง $[l_i, r_i]$ และ $[l_j, r_j]$ หรือกล่าวอย่างเป็นทางการคือ ค่าใช้จ่ายเท่ากับ $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$
จงหาต้นไม้แผ่ทั่วที่มีน้ำหนักน้อยที่สุด (minimum spanning tree) ของกราฟที่อธิบายไว้
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม $2$ ตัว คือ $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — ความยาวของเพอร์มิวเทชันและจำนวนช่วง
บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ ตัว คือ $p_i$ ($0 \le p_i \le n - 1$) — รายละเอียดของเพอร์มิวเทชัน $p$
อีก $m$ บรรทัดถัดไปประกอบด้วยคู่ของจำนวนเต็ม $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — รายละเอียดของแต่ละช่วง
ข้อมูลส่งออก
ในบรรทัดเดียว ให้แสดงผลคำตอบของปัญหานี้
ตัวอย่าง
ข้อมูลนำเข้า 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
ข้อมูลส่งออก 1
8
ข้อมูลนำเข้า 2
2 2 0 1 1 2 1 2
ข้อมูลส่งออก 2
2