Определим $\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