Definamos $\operatorname{mex}(S)$ como el menor entero no negativo que no está contenido en $S$.
Se te da una permutación $p$ que consta de $n$ elementos de $0$ a $n - 1$. También tienes $m$ segmentos $[l_i, r_i]$ que utilizas para construir un grafo de la siguiente manera:
- Para cada par de vértices $i \neq j$, añades una arista con costo igual al $\operatorname{mex}$ de la unión de los valores de la permutación en los segmentos $[l_i, r_i]$ y $[l_j, r_j]$. Más formalmente, el costo es igual a $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Encuentra el árbol recubridor mínimo del grafo descrito.
Entrada
La primera línea contiene $2$ enteros $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — la longitud de la permutación y el número de segmentos.
La segunda línea contiene $n$ enteros $p_i$ ($0 \le p_i \le n - 1$) — la descripción de la permutación $p$.
Las siguientes $m$ líneas contienen pares de enteros $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — la descripción de los segmentos.
Salida
En una sola línea, imprime la respuesta al problema.
Ejemplos
Entrada 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Salida 1
8
Entrada 2
2 2 0 1 1 2 1 2
Salida 2
2