Функция называется Липшицевой, если найдётся такое действительное число K, что неравенство |f(x) - f(y)| ≤ K·|x - y| выполняется для всех . Мы будем иметь дело с более... дискретным вариантом этого термина.
Для массива определим его константу Липшица следующим образом:
Другими словами, — это наименьшее неотрицательное целое число, такое, что |h[i] - h[j]| ≤ L·|i - j| выполняется для всех 1 ≤ i, j ≤ n.
Вам дан массив размера n и q запросов вида [l, r]. Для каждого запроса рассмотрим подмассив ; определите сумму констант Липшица всех подмассивов .
В первой строке входных данных записано два числ n и q (2 ≤ n ≤ 100 000, 1 ≤ q ≤ 100) — длина массива и количество запросов соответственно.
Во второй строке записано n целых чисел ().
Следующие q строк описывают запросы, i-я из них содержит два числа li и ri (1 ≤ li < ri ≤ n).
Выведите ответы на все запросы в том порядке, в котором они даны во входных данных. Для i-го запроса выведите единственное целое число — сумму констант Липшица всех подмассивов .
В первом запросе первого примера константы Липшица подмассивов длиной не менее 2 таковы:
Ответом на запрос является их сумма.
10 4 1 5 2 9 1 3 4 2 1 7 2 4 3 8 7 10 1 9
17 82 23 210
7 6 5 7 7 4 6 6 2 1 2 2 3 2 6 1 7 4 7 3 5
2 0 22 59 16 8
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач