我們定義 $\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