如果存在实数常数 K 且不等式 |f(x) - f(y)|,则函数 $$f : \mathbb{R} \to \mathbb{R}$$ 称为 Lipschitz 连续函数≤ K·|x - y|对于 \mathbb{R}$$ 中的所有 $$x,y 成立。我们将处理这个术语的一个更......离散的版本。
对于数组 $$h[1..n]$$,我们定义它的 Lipschitz 常量 $${\cal L}({\bf h})$$ 如下:
- 如果 n < 2,$$L(\mathbf{h}) = 0$$
- 如果 n ≥ 2,$${\displaystyle L(h)=\max \left\{{\frac {|h[j]-h[i]|}{j-i}}\right\}}$$ 超过所有 1 ≤ i < j ≤ n
换句话说,$$L = L(h)$$ 是满足 |h[i] - h[j]| 的最小非负整数。 ≤ L·|i - j|对于所有 1 ≤ i, j ≤ n 成立。
给定一个大小为 n 的数组 $$\alpha$$ 和 [l, r] 形式的 q 个查询。对于每个查询,考虑子数组 $$s = a[l..r]$$;确定 ? 的所有子数组的 Lipschitz 常数之和。
输入
输入的第一行包含两个空格分隔的整数 n 和 q(2 ≤ n ≤ 100 000 和 1 ≤ q ≤ 100)——分别是数组 $$\alpha$$ 中的元素数量和查询数量。
第二行包含 n 个空格分隔的整数 $${\mathbf{a}}^{[1..n]}$$ ($$0 \leq a[i] \leq 10^8$$)。
以下 q 行描述查询。这些行的第 i 行包含两个空格分隔的整数 li 和 ri (1 ≤ li < ri ≤ n)。
输出
按照输入中给出的顺序打印所有查询的答案。对于第 i 个查询,打印一行,其中包含一个整数 - $$a[l_i..r_i]$$ 的所有子数组的 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
注意
在第一个样本的第一个查询中,长度至少为 2 的 $$[5,2,9]$$ 子数组的 Lipschitz 常量为:
- $${\cal L}([5,2])=3$$
- $$L([2,9])=7$$
- $$L([5,2,9])=7$$
查询的答案是它们的总和。