Вам дан массив $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]$ является оптимальным.