Se te da un arreglo $a$ que consta de $n$ enteros positivos. Sin embargo, faltan algunos elementos de $a$ y han sido reemplazados por ceros.
Define la oscilación de $a$ en un segmento $[\ell, r]$ como $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
Se te dan $q$ segmentos de la forma $[\ell_i, r_i]$. Reemplaza cada cero en $a$ por un entero positivo para minimizar la suma de las oscilaciones de $a$ en todos los $q$ segmentos.
Entrada
La primera línea contiene dos enteros $n$ y $q$ ($1 \le n, q \le 2 \cdot 10^5$).
La segunda línea contiene $n$ enteros $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): los elementos del arreglo. Aquí, $a_i = 0$ significa que falta el $i$-ésimo elemento.
Las siguientes $q$ líneas describen los segmentos. Cada una de ellas contiene dos enteros $\ell_i$ y $r_i$ ($1 \le \ell_i \le r_i \le n$).
Salida
Imprime un único entero: la suma mínima de las oscilaciones de $a$ en todos los segmentos dados.
Ejemplos
Entrada 1
5 2 2 1 0 3 2 1 3 3 5
Salida 1
2
Entrada 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Salida 2
2
Entrada 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Salida 3
6
Nota
En el primer ejemplo, el único arreglo óptimo es $a = [2, 1, 2, 3, 2]$.
En el segundo ejemplo, hay varios arreglos óptimos. Por ejemplo, $a = [1, 2, 3, 2, 1]$ es óptimo.
En el tercer ejemplo, hay varios arreglos óptimos. Por ejemplo, $a = [4, 4, 4, 1, 2, 3, 4]$ es óptimo.