Du får en tabell $a$ som består av $n$ positive heltall. Noen elementer i $a$ mangler imidlertid, og de er erstattet med nuller.
Definer oscillasjonen til $a$ på et segment $[\ell, r]$ til å være $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
Du får $q$ segmenter på formen $[\ell_i, r_i]$. Erstatt hver null i $a$ med et positivt heltall for å minimere summen av oscillasjonene til $a$ på alle de $q$ segmentene.
Inndata
Den første linjen inneholder to heltall $n$ og $q$ ($1 \le n, q \le 2 \cdot 10^5$).
Den andre linjen inneholder $n$ heltall $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): elementene i tabellen. Her betyr $a_i = 0$ at det $i$-te elementet mangler.
De neste $q$ linjene beskriver segmentene. Hver av dem inneholder to heltall $\ell_i$ og $r_i$ ($1 \le \ell_i \le r_i \le n$).
Utdata
Skriv ut et enkelt heltall: den minimale summen av oscillasjonene til $a$ på alle de gitte segmentene.
Eksempler
Inndata 1
5 2 2 1 0 3 2 1 3 3 5
Utdata 1
2
Inndata 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Utdata 2
2
Inndata 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Utdata 3
6
Forklaring
I det første eksempelet er den eneste optimale tabellen $a = [2, 1, 2, 3, 2]$.
I det andre eksempelet finnes det flere optimale tabeller. For eksempel er $a = [1, 2, 3, 2, 1]$ optimal.
I det tredje eksempelet finnes det flere optimale tabeller. For eksempel er $a = [4, 4, 4, 1, 2, 3, 4]$ optimal.