Anda diberikan sebuah larik $a$ yang terdiri atas $n$ bilangan bulat positif. Namun, beberapa elemen dari $a$ hilang, dan elemen-elemen tersebut digantikan oleh angka nol.
Definisikan osilasi dari $a$ pada suatu segmen $[\ell, r]$ sebagai $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
Anda diberikan $q$ segmen berbentuk $[\ell_i, r_i]$. Gantilah setiap angka nol di $a$ dengan suatu bilangan bulat positif untuk meminimalkan jumlah osilasi dari $a$ pada semua $q$ segmen tersebut.
Masukan
Baris pertama berisi dua bilangan bulat $n$ dan $q$ ($1 \le n, q \le 2 \cdot 10^5$).
Baris kedua berisi $n$ bilangan bulat $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): elemen-elemen dari larik. Di sini, $a_i = 0$ berarti bahwa elemen ke-$i$ hilang.
$q$ baris berikutnya mendeskripsikan segmen-segmen tersebut. Masing-masing baris berisi dua bilangan bulat $\ell_i$ dan $r_i$ ($1 \le \ell_i \le r_i \le n$).
Keluaran
Cetaklah satu bilangan bulat: jumlah osilasi minimum dari $a$ pada semua segmen yang diberikan.
Contoh
Masukan 1
5 2 2 1 0 3 2 1 3 3 5
Keluaran 1
2
Masukan 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Keluaran 2
2
Masukan 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Keluaran 3
6
Catatan
Pada contoh pertama, satu-satunya larik yang optimal adalah $a = [2, 1, 2, 3, 2]$.
Pada contoh kedua, terdapat beberapa larik yang optimal. Sebagai contoh, $a = [1, 2, 3, 2, 1]$ adalah optimal.
Pada contoh ketiga, terdapat beberapa larik yang optimal. Sebagai contoh, $a = [4, 4, 4, 1, 2, 3, 4]$ adalah optimal.