On vous donne un tableau $a$ composé de $n$ entiers strictement positifs. Cependant, certains éléments de $a$ sont manquants et ont été remplacés par des zéros.
On définit l'oscillation de $a$ sur un segment $[\ell, r]$ comme étant $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
On vous donne $q$ segments de la forme $[\ell_i, r_i]$. Remplacez chaque zéro dans $a$ par un entier strictement positif afin de minimiser la somme des oscillations de $a$ sur l'ensemble des $q$ segments.
Entrée
La première ligne contient deux entiers $n$ et $q$ ($1 \le n, q \le 2 \cdot 10^5$).
La deuxième ligne contient $n$ entiers $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$) : les éléments du tableau. Ici, $a_i = 0$ signifie que le $i$-ième élément est manquant.
Les $q$ lignes suivantes décrivent les segments. Chacune d'elles contient deux entiers $\ell_i$ et $r_i$ ($1 \le \ell_i \le r_i \le n$).
Sortie
Affichez un seul entier : la somme minimale des oscillations de $a$ sur tous les segments donnés.
Exemples
Entrée 1
5 2 2 1 0 3 2 1 3 3 5
Sortie 1
2
Entrée 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Sortie 2
2
Entrée 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Sortie 3
6
Remarque
Dans le premier exemple, le seul tableau optimal est $a = [2, 1, 2, 3, 2]$.
Dans le deuxième exemple, il existe plusieurs tableaux optimaux. Par exemple, $a = [1, 2, 3, 2, 1]$ est optimal.
Dans le troisième exemple, il existe plusieurs tableaux optimaux. Par exemple, $a = [4, 4, 4, 1, 2, 3, 4]$ est optimal.