Визначимо $\operatorname{mex}(S)$ як мінімальне невід'ємне ціле число, яке не міститься в $S$.
Вам дано перестановку $p$, що складається з $n$ елементів від $0$ до $n - 1$. Також у вас є $m$ відрізків $[l_i, r_i]$, за допомогою яких будується граф таким чином:
- Для кожної пари вершин $i \neq j$ додається ребро з вартістю, що дорівнює $\operatorname{mex}$ об'єднання значень перестановки на відрізках $[l_i, r_i]$ та $[l_j, r_j]$. Більш формально, вартість дорівнює $\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