$\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