$\operatorname{mex}(S)$ を、集合 $S$ に含まれない最小の非負整数として定義します。
$0$ から $n - 1$ までの $n$ 個の要素からなる順列 $p$ が与えられます。また、$m$ 個の区間 $[l_i, r_i]$ が与えられ、これらを用いて以下のようにグラフを構築します:
- 異なる頂点の各組 $i \neq j$ について、順列の区間 $[l_i, r_i]$ と $[l_j, r_j]$ における値の和集合の $\operatorname{mex}$ に等しいコストを持つ辺を追加する。より正確には、コストは $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$ に等しい。
このグラフの最小全域木を求めてください。
入力
最初の行には $2$ 個の整数 $n, m$($2 \le n, m \le 3 \cdot 10^5$)が与えられます。これらは順列の長さと区間の個数を表します。
2 行目には $n$ 個の整数 $p_i$($0 \le p_i \le n - 1$)が与えられ、順列 $p$ を表します。
続く $m$ 行には整数の組 $l_i, r_i$($1 \le l_i \le r_i \le n$)が与えられ、各区間を表します。
出力
1 行に問題の答えを出力してください。
入出力例
入力 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
出力 1
8
入力 2
2 2 0 1 1 2 1 2
出力 2
2