定义 $\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]\})$。

求该图的最小生成树的权值和。

输入格式

第一行包含两个整数 $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