Z君的日常之奇怪的函数

题目描述

大家都知道，Z君喜欢数学。这天，他的高数老师给了他一个奇怪的函数 f :R→R，当这个函数满足：存在一个实常数K，对于任意的 x,y∈R ，使得 | f(x) - f(y) | ≤ K * | x - y | 时，我们称这个函数为Lipschitz continuous 。 Z君觉得这个函数太难了，他决定先从数组开始研究。对于一个数组h[1..n]，我们定义Lipschitz 常数L(h):

1.如果n<2，

2.如果n≥2，

换句话说，L=L(h)是对于所有的1 ≤ i, j ≤ n使得|h[i] - h[j]| ≤ L*|i - j|成立的最小非负整数。

现在给你一个大小为n的数组a，和q个询问[l,r]。对于每个询问，设子数组s=a[l..r]；求s的所有连续子数组的Lipschitz 常数的和。

输入

第一行为两个整数n，q ( 2 ≤ n ≤ 100 000，1 ≤ q ≤ 100 ) ——数组a的大小和询问次数。

第二行为n个整数代表a[1..n]， ( 0 ≤ a[i] ≤ 10^8 )。

接下来有q行询问。每行有两个整数 l，r（1 ≤ l ≤ r ≤ n ）。

输出

对于每个询问，输出数组a[l..r]的所有连续子数组的Lipschitz常数的和。

输入样例

10 4
1 5 2 9 1 3 4 2 1 7
2 4
3 8
7 10
1 9

输出样例

17
82
23
210

样例解释

对于第一个询问2 4

L ( [5,2] ) = 3

L ( [2,9] ) = 7

L ( [5,2,9] ) = 7

答案为他们的和3+7+7=17