נגדיר את $\operatorname{mex}(S)$ בתור המספר השלם האי-שלילי הקטן ביותר שאינו מוכל ב-$S$.
נתונה לכם תמורה $p$ המורכבת מ-$n$ איברים מ-$0$ עד $n - 1$. כמו כן נתונים לכם $m$ קטעים $[l_i, r_i]$ שבהם אתם משתמשים כדי לבנות גרף באופן הבא:
- עבור כל זוג קודקודים $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]\})$.
מצאו את העץ הפורש המינימלי של הגרף המתואר.
קלט
השורה הראשונה מכילה $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