我哋定義 $\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$)——排列嘅長度同埋區間嘅數量。
第二行包含 $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
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