Олимпиадный тренинг

Задача . B. Липшицева последовательность

Задача

Функция $\text{[math]}$ называется Липшицевой, если найдётся такое действительное число K, что неравенство |f(x) - f(y)| ≤ K·|x - y| выполняется для всех $\text{[math]}$ . Мы будем иметь дело с более... дискретным вариантом этого термина.

Для массива $\text{[math]}$ определим его константу Липшица $\text{[math]}$ следующим образом:

если n < 2, $\text{[math]}$
если n ≥ 2, $\text{[math]}$ по всем 1 ≤ i < j ≤ n

Другими словами, $\text{[math]}$ — это наименьшее неотрицательное целое число, такое, что |h[i] - h[j]| ≤ L·|i - j| выполняется для всех 1 ≤ i, j ≤ n.

Вам дан массив $\text{[math]}$ размера n и q запросов вида [l, r]. Для каждого запроса рассмотрим подмассив $\text{[math]}$ ; определите сумму констант Липшица всех подмассивов $\text{[math]}$ .

Входные данные

В первой строке входных данных записано два числ n и q (2 ≤ n ≤ 100 000, 1 ≤ q ≤ 100) — длина массива $\text{[math]}$ и количество запросов соответственно.

Во второй строке записано n целых чисел $\text{[math]}$ ( $\text{[math]}$ ).

Следующие q строк описывают запросы, i-я из них содержит два числа l_i и r_i (1 ≤ l_i < r_i ≤ n).

Выходные данные

Выведите ответы на все запросы в том порядке, в котором они даны во входных данных. Для i-го запроса выведите единственное целое число — сумму констант Липшица всех подмассивов $\text{[math]}$ .