Zdefiniujmy $\operatorname{mex}(S)$ jako najmniejszą nieujemną liczbę całkowitą, która nie należy do zbioru $S$.
Dana jest permutacja $p$ składająca się z $n$ elementów od $0$ do $n - 1$. Masz również $m$ przedziałów $[l_i, r_i]$, których używasz do zbudowania grafu w następujący sposób:
- Dla każdej pary wierzchołków $i \neq j$ dodajesz krawędź o koszcie równym $\operatorname{mex}$ sumy zbiorów wartości permutacji na przedziałach $[l_i, r_i]$ oraz $[l_j, r_j]$. Bardziej formalnie, koszt jest równy $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Znajdź minimalne drzewo rozpinające opisanego grafu.
Wejście
Pierwszy wiersz zawiera $2$ liczby całkowite $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — długość permutacji oraz liczbę przedziałów.
Drugi wiersz zawiera $n$ liczb całkowitych $p_i$ ($0 \le p_i \le n - 1$) — opis permutacji $p$.
Kolejne $m$ wierszy zawiera pary liczb całkowitych $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — opis przedziałów.
Wyjście
W jedynym wierszu wypisz odpowiedź dla podanego zadania.
Przykład
Wejście 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Wyjście 1
8
Wejście 2
2 2 0 1 1 2 1 2
Wyjście 2
2