La oss definere $\operatorname{mex}(S)$ som det minste ikke-negative heltallet som ikke er inneholdt i $S$.
Du får gitt en permutasjon $p$ som består av $n$ elementer fra $0$ til $n - 1$. Du har også $m$ segmenter $[l_i, r_i]$ som du bruker til å bygge en graf på følgende måte:
- For hvert par av noder $i \neq j$ legger du til en kant med kostnad lik $\operatorname{mex}$ av unionen av verdiene til permutasjonen på segmentene $[l_i, r_i]$ og $[l_j, r_j]$. Mer formelt er kostnaden lik $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Finn det minimale spenntreet i den beskrevne grafen.
Inndata
Den første linjen inneholder $2$ heltall $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — lengden på permutasjonen og antallet segmenter.
Den andre linjen inneholder $n$ heltall $p_i$ ($0 \le p_i \le n - 1$) — beskrivelsen av permutasjonen $p$.
De neste $m$ linjene inneholder par av heltall $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — beskrivelsen av segmentene.
Utdata
Skriv ut svaret på oppgaven på en enkelt linje.
Eksempler
Inndata 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Utdata 1
8
Inndata 2
2 2 0 1 1 2 1 2
Utdata 2
2