Du får en array $a$ som består av $n$ positiva heltal. Vissa element i $a$ saknas dock och har ersatts med nollor.
Definiera oscillationen av $a$ på ett segment $[\ell, r]$ som $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
Du får $q$ segment på formen $[\ell_i, r_i]$. Ersätt varje nolla i $a$ med ett positivt heltal för att minimera summan av oscillationerna av $a$ på alla $q$ segment.
Indata
Den första raden innehåller två heltal $n$ och $q$ ($1 \le n, q \le 2 \cdot 10^5$).
Den andra raden innehåller $n$ heltal $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): elementen i arrayen. Här betyder $a_i = 0$ att det $i$-te elementet saknas.
De följande $q$ raderna beskriver segmenten. Var och en av dem innehåller två heltal $\ell_i$ och $r_i$ ($1 \le \ell_i \le r_i \le n$).
Utdata
Skriv ut ett enda heltal: den minimala summan av oscillationerna av $a$ på alla givna segment.
Exempel
Indata 1
5 2 2 1 0 3 2 1 3 3 5
Utdata 1
2
Indata 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Utdata 2
2
Indata 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Utdata 3
6
Förklaring
I det första exemplet är den enda optimala arrayen $a = [2, 1, 2, 3, 2]$.
I det andra exemplet finns det flera optimala arrayer. Till exempel är $a = [1, 2, 3, 2, 1]$ optimal.
I det tredje exemplet finns det flera optimala arrayer. Till exempel är $a = [4, 4, 4, 1, 2, 3, 4]$ optimal.