Skilgreinum $\operatorname{mex}(S)$ sem minnstu óneikvæðu heiltöluna sem er ekki í $S$.
Gefin er umröðun $p$ sem samanstendur af $n$ stökum frá $0$ til $n - 1$. Einnig eru gefin $m$ bil $[l_i, r_i]$ sem notuð eru til að smíða net á eftirfarandi hátt:
- Fyrir hvert par hnúta $i \neq j$ er bætt við legg með kostnað sem er jafn $\operatorname{mex}$ af sammengi gilda umröðunarinnar á bilunum $[l_i, r_i]$ og $[l_j, r_j]$. Formlegar sagt er kostnaðurinn jafn $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Finndu minnsta spanntré netsins sem lýst er.
Inntak
Fyrsta línan inniheldur $2$ heiltölur $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — lengd umröðunarinnar og fjölda bila.
Önnur línan inniheldur $n$ heiltölur $p_i$ ($0 \le p_i \le n - 1$) — lýsingu á umröðuninni $p$.
Næstu $m$ línur innihalda pör af heiltölum $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — lýsingu á bilunum.
Úttak
Prentaðu svarið við verkefninu í einni línu.
Dæmi
Inntak 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Úttak 1
8
Inntak 2
2 2 0 1 1 2 1 2
Úttak 2
2