Låt oss definiera $\operatorname{mex}(S)$ som det minsta icke-negativa heltalet som inte finns i $S$.
Du får en permutation $p$ bestående av $n$ element från $0$ till $n - 1$. Du har också $m$ segment $[l_i, r_i]$ som du använder för att bygga en graf på följande sätt:
- För varje par av hörn $i \neq j$ lägger du till en kant med kostnad lika med $\operatorname{mex}$ av unionen av permutationens värden på segmenten $[l_i, r_i]$ och $[l_j, r_j]$. Mer formellt är kostnaden lika med $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Hitta det minimala uppspännande trädet i den beskrivna grafen.
Indata
Den första raden innehåller $2$ heltal $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — permutationens längd och antalet segment.
Den andra raden innehåller $n$ heltal $p_i$ ($0 \le p_i \le n - 1$) — beskrivningen av permutationen $p$.
De följande $m$ raderna innehåller par av heltal $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — beskrivningen av segmenten.
Utdata
Skriv på en enda rad ut svaret på problemet.
Exempel
Indata 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Utdata 1
8
Indata 2
2 2 0 1 1 2 1 2
Utdata 2
2