Mari kita definisikan $\operatorname{mex}(S)$ sebagai bilangan bulat non-negatif terkecil yang tidak terdapat di dalam $S$.
Anda diberikan sebuah permutasi $p$ yang terdiri dari $n$ elemen dari $0$ hingga $n - 1$. Anda juga memiliki $m$ segmen $[l_i, r_i]$ yang digunakan untuk membangun sebuah graf dengan cara berikut:
- Untuk setiap pasangan simpul $i \neq j$, Anda menambahkan sebuah sisi dengan biaya yang sama dengan $\operatorname{mex}$ dari gabungan nilai-nilai permutasi pada segmen $[l_i, r_i]$ dan $[l_j, r_j]$. Secara lebih formal, biayanya sama dengan $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Temukan pohon merentang minimum (minimum spanning tree) dari graf yang dijelaskan tersebut.
Masukan
Baris pertama berisi $2$ bilangan bulat $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — panjang permutasi dan banyaknya segmen.
Baris kedua berisi $n$ bilangan bulat $p_i$ ($0 \le p_i \le n - 1$) — deskripsi permutasi $p$.
$m$ baris berikutnya berisi pasangan bilangan bulat $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — deskripsi segmen-segmen tersebut.
Keluaran
Dalam satu baris, cetak jawaban dari persoalan ini.
Contoh
Masukan 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Keluaran 1
8
Masukan 2
2 2 0 1 1 2 1 2
Keluaran 2
2