Gefið er fylki $a$ sem samanstendur af $n$ jákvæðum heiltölum. Hins vegar vantar nokkur stök í $a$, og þau hafa verið sett sem núll.
Skilgreinum sveiflu (oscillation) fylkisins $a$ á bili $[\ell, r]$ sem $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
Gefin eru $q$ bil á forminu $[\ell_i, r_i]$. Skiptu hverju núlli í $a$ út fyrir jákvæða heiltölu til að lágmarka summu sveiflna $a$ á öllum $q$ bilunum.
Inntak
Fyrsta línan inniheldur tvær heiltölur $n$ og $q$ ($1 \le n, q \le 2 \cdot 10^5$).
Önnur línan inniheldur $n$ heiltölur $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): stök fylkisins. Hér þýðir $a_i = 0$ að $i$-ta stakið vanti.
Næstu $q$ línur lýsa bilunum. Hver þeirra inniheldur tvær heiltölur $\ell_i$ og $r_i$ ($1 \le \ell_i \le r_i \le n$).
Úttak
Prentaðu eina heiltölu: lágmarkssummu sveiflna $a$ á öllum gefnu bilunum.
Dæmi
Inntak 1
5 2 2 1 0 3 2 1 3 3 5
Úttak 1
2
Inntak 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Úttak 2
2
Inntak 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Úttak 3
6
Athugasemd
Í fyrsta dæminu er eina besta fylkið $a = [2, 1, 2, 3, 2]$.
Í öðru dæminu eru nokkur bestu fylki. Til dæmis er $a = [1, 2, 3, 2, 1]$ best.
Í þriðja dæminu eru nokkur bestu fylki. Til dæmis er $a = [4, 4, 4, 1, 2, 3, 4]$ best.