U283442 奇怪的函数

大家都知道，Z 君喜欢数学。这天，他的高数老师给了他一个奇怪的函数 $f :R→R$，当这个函数满足：存在一个实常数$K$，对于任意的 $x,y∈R$ ，使得 $| f(x) - f(y) | ≤ K | x - y |$ 时，我们称这个函数为 `Lipschitz continuous` 。 现在给你一个大小为 $n$ 的数组 $a $，和 $q$ 个询问 $[l,r]$。对于每个询问，设子数组$s=a[l..r]$；求 $s$ 的所有连续子数组的 `Lipschitz` 常数的和。

Z 君觉得这个函数太难了，他决定先从数组开始研究。对于一个数组 $h[1..n]$ ，我们定义Lipschitz 常数 $L(h)$ : 1. 如果 $n

第一行为两个整数 $n,q$ 代表数组 $a$ 的大小和询问次数。 第二行为 $n$ 个整数代表 $a_1,...,a_n$， ($ 0 ≤ a_i ≤ 10^9 $)。 接下来有 $q$ 行询问。每行有两个整数 $l,r~(1 ≤ l ≤ r ≤ n )$。

对于每个询问，输出数组 $a_l,...,a_r$ 的所有连续子数组的 `Lipschitz` 常数的和。

### 样例解释 对于第一个询问 $2, 4$ - $L ( [5,2] ) = 3$ - $L ( [2,9] ) = 7$ - $L ( [5,2,9] ) = 7$ 答案为他们的和 $3+7+7=17$ ## 数据范围 对于 $10\%$ 的数据有 : $n,q\le 100$ 对于 $30\%$ 的数据有 : $n\times q \le 10^7$ 对于 $100\%$ 的数据有 : $n,q\le 10^5$