Let us define $\operatorname{mex}(S)$ as the minimal non-negative integer which is not contained in $S$.
You are given a permutation $p$ consisting of $n$ elements from $0$ to $n - 1$. You also have $m$ segments $[l_i, r_i]$ which you use to build a graph in the following way:
- For each pair of vertices $i \neq j$, you add an edge with cost equal to the $\operatorname{mex}$ of the union of values of the permutation on segments $[l_i, r_i]$ and $[l_j, r_j]$. More formally, the cost is equal to $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Find the minimum spanning tree of the described graph.
Input
The first line contains $2$ integers $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — length of the permutation and number of segments.
The second line contains $n$ integers $p_i$ ($0 \le p_i \le n - 1$) — description of permutation $p$.
Next $m$ lines contain pairs of integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — description of the segments.
Output
In a single line, output the answer to the problem.
Examples
Input 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Output 1
8
Input 2
2 2 0 1 1 2 1 2
Output 2
2