[问题描述]
大 M 为了正在学习函数的光滑性并对 Lipschitz 常数非常感兴趣：当一个定
义域为[l,r]的函数 f，对于定义域内的任意 x,y 都有|f(x)-f(y)|<=K*|x-y|时，
则称 K 的最小值为该函数在[l,r]上的 Lipschitz 常数。
然而大M 并不满足于函数，所以他定义：对于一个序列 v[1..n]，当 1<=x<y<=n
且 x,y 均为整数时，同样满足|v[x]-v[y]|<=K*|x-y|，则称 K 的最小整数值为序
列 v 的 Lipschitz 常数。
现在给你一个长度为n的序列v[1..n]并给出q个询问，对于每对询问[l,r]，
你需要求出 v[l..r]的所有子序列 v[x..y]（l<=x<y<=r）的 Lipschitz 常数之和。
这可难不倒会编程的你。
[输入格式]
第一行两个整数 n 和 q，分别表示序列的长度以及询问的个数。
第二行 n 个数，表示 v[1..n]，0<=v[i]<=10^8。
接下来 q 行，每行两个数 l 和 r，表示询问的区间为[l..r]。
[输出格式]
对于每个询问，输出一行一个数，即 v[l..r]的所有子序列的 Lipschitz 常
数之和。
[输入样例 1]
10 4
1 5 2 9 1 3 4 2 1 7
2 4
3 8
7 10
1 9
[输出样例 1]
17
82
23
210
[输入样例 2]
7 6
5 7 7 4 6 6 2
1 2
2 3
2 6
1 7
4 7
3 5
[输出样例 2]
2
0
22
59
16
8
[数据规模]
对于 30%的数据，n<=500；
对于 60%的数据，n<=50000；
对于 100%的数据，n<=100000,q<=100。