Wir definieren $\operatorname{mex}(S)$ als die kleinste nichtnegative ganze Zahl, die nicht in $S$ enthalten ist.
Gegeben ist eine Permutation $p$, die aus $n$ Elementen von $0$ bis $n - 1$ besteht. Außerdem hast du $m$ Intervalle $[l_i, r_i]$, mit denen du auf folgende Weise einen Graphen konstruierst:
- Für jedes Paar von Knoten $i \neq j$ fügst du eine Kante hinzu, deren Kosten gleich dem $\operatorname{mex}$ der Vereinigung der Werte der Permutation auf den Intervallen $[l_i, r_i]$ und $[l_j, r_j]$ sind. Formaler ausgedrückt sind die Kosten gleich $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Bestimme den minimalen Spannbaum des beschriebenen Graphen.
Eingabe
Die erste Zeile enthält $2$ ganze Zahlen $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — die Länge der Permutation und die Anzahl der Intervalle.
Die zweite Zeile enthält $n$ ganze Zahlen $p_i$ ($0 \le p_i \le n - 1$) — die Beschreibung der Permutation $p$.
Die nächsten $m$ Zeilen enthalten Paare ganzer Zahlen $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — die Beschreibung der Intervalle.
Ausgabe
Gib in einer einzigen Zeile die Antwort auf das Problem aus.
Beispiele
Eingabe 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Ausgabe 1
8
Eingabe 2
2 2 0 1 1 2 1 2
Ausgabe 2
2