Ta định nghĩa $\operatorname{mex}(S)$ là số nguyên không âm nhỏ nhất không nằm trong $S$.
Bạn được cho một hoán vị $p$ gồm $n$ phần tử từ $0$ đến $n - 1$. Bạn cũng có $m$ đoạn $[l_i, r_i]$ dùng để xây dựng một đồ thị theo cách sau:
- Với mỗi cặp đỉnh $i \neq j$, bạn thêm một cạnh có chi phí bằng $\operatorname{mex}$ của hợp các giá trị của hoán vị trên hai đoạn $[l_i, r_i]$ và $[l_j, r_j]$. Một cách hình thức hơn, chi phí bằng $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
Hãy tìm cây khung nhỏ nhất của đồ thị được mô tả.
Dữ liệu vào
Dòng đầu tiên chứa $2$ số nguyên $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — độ dài của hoán vị và số lượng đoạn.
Dòng thứ hai chứa $n$ số nguyên $p_i$ ($0 \le p_i \le n - 1$) — mô tả hoán vị $p$.
$m$ dòng tiếp theo chứa các cặp số nguyên $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — mô tả các đoạn.
Dữ liệu ra
Trên một dòng duy nhất, in ra đáp án của bài toán.
Ví dụ
Dữ liệu vào 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
Dữ liệu ra 1
8
Dữ liệu vào 2
2 2 0 1 1 2 1 2
Dữ liệu ra 2
2