Définissons $\operatorname{mex}(S)$ comme le plus petit entier naturel (positif ou nul) qui n'appartient pas à $S$.
On vous donne une permutation $p$ composée de $n$ éléments allant de $0$ à $n - 1$. Vous disposez également de $m$ segments $[l_i, r_i]$ que vous utilisez pour construire un graphe de la manière suivante :
- Pour chaque paire de sommets $i \neq j$, vous ajoutez une arête dont le coût est égal au $\operatorname{mex}$ de l'union des valeurs de la permutation sur les segments $[l_i, r_i]$ et $[l_j, r_j]$. Plus formellement, le coût est égal à $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Trouvez l'arbre couvrant de poids minimum du graphe décrit.
Entrée
La première ligne contient $2$ entiers $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — la longueur de la permutation et le nombre de segments.
La deuxième ligne contient $n$ entiers $p_i$ ($0 \le p_i \le n - 1$) — la description de la permutation $p$.
Les $m$ lignes suivantes contiennent des paires d'entiers $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — la description des segments.
Sortie
Sur une seule ligne, affichez la réponse au problème.
Exemples
Entrée 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Sortie 1
8
Entrée 2
2 2 0 1 1 2 1 2
Sortie 2
2