Вам дано масив $a$, що складається з $n$ додатних цілих чисел. Проте деякі елементи масиву $a$ пропущені й замінені нулями.
Визначимо коливання масиву $a$ на відрізку $[\ell, r]$ як $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
Вам дано $q$ відрізків вигляду $[\ell_i, r_i]$. Замініть кожен нуль в $a$ додатним цілим числом так, щоб мінімізувати суму коливань масиву $a$ на всіх $q$ відрізках.
Вхідні дані
Перший рядок містить два цілі числа $n$ і $q$ ($1 \le n, q \le 2 \cdot 10^5$).
Другий рядок містить $n$ цілих чисел $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$) — елементи масиву. Тут $a_i = 0$ означає, що $i$-й елемент пропущено.
Наступні $q$ рядків описують відрізки. Кожен із них містить два цілі числа $\ell_i$ та $r_i$ ($1 \le \ell_i \le r_i \le n$).
Вихідні дані
Виведіть одне ціле число — мінімальну суму коливань масиву $a$ на всіх заданих відрізках.
Приклади
Вхідні дані 1
5 2 2 1 0 3 2 1 3 3 5
Вихідні дані 1
2
Вхідні дані 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Вихідні дані 2
2
Вхідні дані 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Вихідні дані 3
6
Примітка
У першому прикладі єдиний оптимальний масив — це $a = [2, 1, 2, 3, 2]$.
У другому прикладі існує декілька оптимальних масивів. Наприклад, масив $a = [1, 2, 3, 2, 1]$ є оптимальним.
У третьому прикладі існує декілька оптимальних масивів. Наприклад, масив $a = [4, 4, 4, 1, 2, 3, 4]$ є оптимальним.