Dana jest tablica $a$ składająca się z $n$ dodatnich liczb całkowitych. Jednak niektóre elementy tablicy $a$ zostały utracone i zastąpiono je zerami.
Zdefiniujmy wahanie tablicy $a$ na przedziale $[\ell, r]$ jako $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
Danych jest $q$ przedziałów postaci $[\ell_i, r_i]$. Zastąp każde zero w tablicy $a$ pewną dodatnią liczbą całkowitą tak, aby zminimalizować sumę wahań tablicy $a$ na wszystkich $q$ przedziałach.
Wejście
Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $q$ ($1 \le n, q \le 2 \cdot 10^5$).
Drugi wiersz zawiera $n$ liczb całkowitych $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): elementy tablicy. Tutaj $a_i = 0$ oznacza, że brakuje $i$-tego elementu.
Kolejne $q$ wierszy opisuje przedziały. Każdy z nich zawiera dwie liczby całkowite $\ell_i$ oraz $r_i$ ($1 \le \ell_i \le r_i \le n$).
Wyjście
Wypisz jedną liczbę całkowitą: minimalną sumę wahań tablicy $a$ na wszystkich podanych przedziałach.
Przykład
Wejście 1
5 2 2 1 0 3 2 1 3 3 5
Wyjście 1
2
Wejście 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Wyjście 2
2
Wejście 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Wyjście 3
6
Uwagi
W pierwszym przykładzie jedyną optymalną tablicą jest $a = [2, 1, 2, 3, 2]$.
W drugim przykładzie istnieje kilka optymalnych tablic. Na przykład tablica $a = [1, 2, 3, 2, 1]$ jest optymalna.
W trzecim przykładzie istnieje kilka optymalnych tablic. Na przykład tablica $a = [4, 4, 4, 1, 2, 3, 4]$ jest optymalna.