Gegeben ist ein Array $a$, das aus $n$ positiven ganzen Zahlen besteht. Allerdings fehlen einige Elemente von $a$, und sie wurden durch Nullen ersetzt.
Definiere die Oszillation von $a$ auf einem Segment $[\ell, r]$ als $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
Gegeben sind $q$ Segmente der Form $[\ell_i, r_i]$. Ersetze jede Null in $a$ durch eine positive ganze Zahl, um die Summe der Oszillationen von $a$ auf allen $q$ Segmenten zu minimieren.
Eingabe
Die erste Zeile enthält zwei ganze Zahlen $n$ und $q$ ($1 \le n, q \le 2 \cdot 10^5$).
Die zweite Zeile enthält $n$ ganze Zahlen $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): die Elemente des Arrays. Hierbei bedeutet $a_i = 0$, dass das $i$-te Element fehlt.
Die nächsten $q$ Zeilen beschreiben die Segmente. Jede von ihnen enthält zwei ganze Zahlen $\ell_i$ und $r_i$ ($1 \le \ell_i \le r_i \le n$).
Ausgabe
Gib eine einzige ganze Zahl aus: die minimale Summe der Oszillationen von $a$ auf allen gegebenen Segmenten.
Beispiele
Eingabe 1
5 2 2 1 0 3 2 1 3 3 5
Ausgabe 1
2
Eingabe 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Ausgabe 2
2
Eingabe 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Ausgabe 3
6
Hinweis
Im ersten Beispiel ist das einzige optimale Array $a = [2, 1, 2, 3, 2]$.
Im zweiten Beispiel gibt es mehrere optimale Arrays. Zum Beispiel ist $a = [1, 2, 3, 2, 1]$ optimal.
Im dritten Beispiel gibt es mehrere optimale Arrays. Zum Beispiel ist $a = [4, 4, 4, 1, 2, 3, 4]$ optimal.