Annettuna on taulukko $a$, joka koostuu $n$ positiivisesta kokonaisluvusta. Jotkin taulukon $a$ alkiot kuitenkin puuttuvat, ja ne on korvattu nollilla.
Määritellään taulukon $a$ vaihtelu välillä $[\ell, r]$ lausekkeena $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
Annettuna on $q$ muotoa $[\ell_i, r_i]$ olevaa väliä. Korvaa jokainen taulukon $a$ nolla positiivisella kokonaisluvulla siten, että taulukon $a$ vaihteluiden summa kaikilla $q$ välillä on mahdollisimman pieni.
Syöte
Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $q$ ($1 \le n, q \le 2 \cdot 10^5$).
Toisella rivillä on $n$ kokonaislukua $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): taulukon alkiot. Tässä $a_i = 0$ tarkoittaa, että $i$-s alkio puuttuu.
Seuraavat $q$ riviä kuvaavat välit. Jokaisella niistä on kaksi kokonaislukua $\ell_i$ ja $r_i$ ($1 \le \ell_i \le r_i \le n$).
Tuloste
Tulosta yksi kokonaisluku: taulukon $a$ vaihteluiden pienin mahdollinen summa kaikilla annetuilla väleillä.
Esimerkit
Syöte 1
5 2 2 1 0 3 2 1 3 3 5
Tuloste 1
2
Syöte 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Tuloste 2
2
Syöte 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Tuloste 3
6
Huomautus
Ensimmäisessä esimerkissä ainoa optimaalinen taulukko on $a = [2, 1, 2, 3, 2]$.
Toisessa esimerkissä optimaalisia taulukoita on useita. Esimerkiksi $a = [1, 2, 3, 2, 1]$ on optimaalinen.
Kolmannessa esimerkissä optimaalisia taulukoita on useita. Esimerkiksi $a = [4, 4, 4, 1, 2, 3, 4]$ on optimaalinen.