Määritellään $\operatorname{mex}(S)$ pienimmäksi epänegatiiviseksi kokonaisluvuksi, joka ei sisälly joukkoon $S$.
Sinulle annetaan permutaatio $p$, joka koostuu $n$ alkiosta väliltä $0$ – $n - 1$. Sinulla on myös $m$ väliä $[l_i, r_i]$, joiden avulla muodostat verkon seuraavalla tavalla:
- Jokaiselle solmuparille $i \neq j$ lisätään kaari, jonka paino on permutaation väleillä $[l_i, r_i]$ ja $[l_j, r_j]$ esiintyvien arvojen yhdisteen $\operatorname{mex}$. Täsmällisemmin ilmaistuna paino on $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Etsi kuvatun verkon pienin virittävä puu.
Syöte
Ensimmäinen rivi sisältää $2$ kokonaislukua $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — permutaation pituuden ja välien lukumäärän.
Toinen rivi sisältää $n$ kokonaislukua $p_i$ ($0 \le p_i \le n - 1$) — permutaation $p$ kuvauksen.
Seuraavat $m$ riviä sisältävät kokonaislukupareja $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — välien kuvaukset.
Tuloste
Tulosta yhdelle riville tehtävän vastaus.
Esimerkit
Syöte 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Tuloste 1
8
Syöte 2
2 2 0 1 1 2 1 2
Tuloste 2
2