Definiamo $\operatorname{mex}(S)$ come il minimo intero non negativo che non è contenuto in $S$.
Ti viene data una permutazione $p$ composta da $n$ elementi da $0$ a $n - 1$. Hai anche $m$ segmenti $[l_i, r_i]$ che usi per costruire un grafo nel modo seguente:
- Per ogni coppia di vertici $i \neq j$, aggiungi un arco con costo uguale al $\operatorname{mex}$ dell'unione dei valori della permutazione sui segmenti $[l_i, r_i]$ e $[l_j, r_j]$. Più formalmente, il costo è uguale a $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Trova il minimo albero ricoprente (minimum spanning tree) del grafo descritto.
Input
La prima riga contiene $2$ interi $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — la lunghezza della permutazione e il numero di segmenti.
La seconda riga contiene $n$ interi $p_i$ ($0 \le p_i \le n - 1$) — la descrizione della permutazione $p$.
Le successive $m$ righe contengono coppie di interi $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — la descrizione dei segmenti.
Output
In una singola riga, stampa la risposta al problema.
Esempi
Input 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Output 1
8
Input 2
2 2 0 1 1 2 1 2
Output 2
2