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