Ti viene dato un array $a$ composto da $n$ interi positivi. Tuttavia, alcuni elementi di $a$ sono mancanti e sono stati sostituiti da zeri.
Definisci l'oscillazione di $a$ su un segmento $[\ell, r]$ come $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
Ti vengono dati $q$ segmenti nella forma $[\ell_i, r_i]$. Sostituisci ogni zero in $a$ con un intero positivo per minimizzare la somma delle oscillazioni di $a$ su tutti i $q$ segmenti.
Input
La prima riga contiene due interi $n$ e $q$ ($1 \le n, q \le 2 \cdot 10^5$).
La seconda riga contiene $n$ interi $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): gli elementi dell'array. Qui, $a_i = 0$ significa che l'$i$-esimo elemento è mancante.
Le successive $q$ righe descrivono i segmenti. Ciascuna di esse contiene due interi $\ell_i$ e $r_i$ ($1 \le \ell_i \le r_i \le n$).
Output
Stampa un singolo intero: la somma minima delle oscillazioni di $a$ su tutti i segmenti dati.
Esempi
Input 1
5 2 2 1 0 3 2 1 3 3 5
Output 1
2
Input 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Output 2
2
Input 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Output 3
6
Note
Nel primo esempio, l'unico array ottimale è $a = [2, 1, 2, 3, 2]$.
Nel secondo esempio, ci sono diversi array ottimali. Ad esempio, $a = [1, 2, 3, 2, 1]$ è ottimale.
Nel terzo esempio, ci sono diversi array ottimali. Ad esempio, $a = [4, 4, 4, 1, 2, 3, 4]$ è ottimale.