Bạn được cho một mảng $a$ gồm $n$ số nguyên dương. Tuy nhiên, một số phần tử của $a$ bị thiếu và chúng đã được thay thế bằng các số 0.
Định nghĩa độ dao động của $a$ trên một đoạn $[\ell, r]$ là $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
Bạn được cho $q$ đoạn có dạng $[\ell_i, r_i]$. Hãy thay thế mỗi số 0 trong $a$ bằng một số nguyên dương sao cho tổng độ dao động của $a$ trên tất cả $q$ đoạn là nhỏ nhất.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($1 \le n, q \le 2 \cdot 10^5$).
Dòng thứ hai chứa $n$ số nguyên $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): các phần tử của mảng. Ở đây, $a_i = 0$ có nghĩa là phần tử thứ $i$ bị thiếu.
$q$ dòng tiếp theo mô tả các đoạn. Mỗi dòng chứa hai số nguyên $\ell_i$ và $r_i$ ($1 \le \ell_i \le r_i \le n$).
Dữ liệu ra
In ra một số nguyên duy nhất: tổng độ dao động nhỏ nhất của $a$ trên tất cả các đoạn đã cho.
Ví dụ
Dữ liệu vào 1
5 2 2 1 0 3 2 1 3 3 5
Dữ liệu ra 1
2
Dữ liệu vào 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Dữ liệu ra 2
2
Dữ liệu vào 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Dữ liệu ra 3
6
Ghi chú
Trong ví dụ thứ nhất, mảng tối ưu duy nhất là $a = [2, 1, 2, 3, 2]$.
Trong ví dụ thứ hai, có nhiều mảng tối ưu. Chẳng hạn, $a = [1, 2, 3, 2, 1]$ là tối ưu.
Trong ví dụ thứ ba, có nhiều mảng tối ưu. Chẳng hạn, $a = [4, 4, 4, 1, 2, 3, 4]$ là tối ưu.