3779: 函数
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：5
解决：3
题目描述
大 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 常 数之和。
样例输入 复制
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]
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。