CF601B.Lipshitz Sequence

A function is called Lipschitz continuous if there is a real constant K such that the inequality |f(x) - f(y)| ≤ K·|x - y| holds for all . We'll deal with a more... discrete version of this term.

For an array , we define it's Lipschitz constant as follows:

• if n < 2,
• if n ≥ 2, over all 1 ≤ i < j ≤ n

In other words, is the smallest non-negative integer such that |h[i] - h[j]| ≤ L·|i - j| holds for all 1 ≤ i, j ≤ n.

You are given an array of size n and q queries of the form [l, r]. For each query, consider the subarray ; determine the sum of Lipschitz constants of all subarrays of .

若存在实数常量 $ K $，使得对所有 $ x, y \in \mathbb{R} $ 均满足不等式 $ |f(x) - f(y)| \leq K \cdot |x - y| $，则称函数 $ f $ 是Lipschitz 连续的。本题将探讨该概念的一个更……离散化版本。

对于一个数组 $ h = [h_1, h_2, \dots, h_n] $，我们定义其 Lipschitz 常数 $ L(h) $ 如下：

• 若 $ n < 2 $，则 $ L(h) = 0 $；
• 若 $ n \geq 2 $，则 $ L(h) = \max\limits_{1 \le i < j \le n} \left\lceil \dfrac{|h[i] - h[j]|}{|i - j|} \right\rceil $。

换言之，$ L(h) $ 是满足对所有 $ 1 \le i, j \le n $ 均有 $ |h[i] - h[j]| \le L \cdot |i - j| $ 的最小非负整数。

给定一个长度为 $ n $ 的数组 $ a $ 和 $ q $ 个形如 $ [l, r] $ 的查询。对每个查询，考虑子数组 $ a[l..r] $；请计算该子数组的所有子数组的 Lipschitz 常数之和。

The first line of the input contains two space-separated integers n and q (2 ≤ n ≤ 100 000 and 1 ≤ q ≤ 100) — the number of elements in array and the number of queries respectively.

The second line contains n space-separated integers ().

The following q lines describe queries. The i-th of those lines contains two space-separated integers l__i and r__i (1 ≤ l__i < r__i ≤ n).

输入的第一行包含两个用空格分隔的整数 $n$ 和 $q$（$2 ≤ n ≤ 100\,000$，$1 ≤ q ≤ 100$），分别表示数组 的元素个数和查询次数。

第二行包含 $n$ 个用空格分隔的整数 （）。

接下来的 $q$ 行描述各次查询。其中第 $i$ 行包含两个用空格分隔的整数 $l_i$ 和 $r_i$（$1 ≤ l_i < r_i ≤ n$）。

Print the answers to all queries in the order in which they are given in the input. For the i-th query, print one line containing a single integer — the sum of Lipschitz constants of all subarrays of .

按输入中给出查询的顺序输出所有查询的答案。对于第 i 个查询，输出一行，包含一个整数——即数组 的所有子数组的 Lipschitz 常数之和。

In the first query of the first sample, the Lipschitz constants of subarrays of with length at least 2 are:

• 
• 
• 

The answer to the query is their sum.

在第一个样例的第一个查询中，长度至少为 2 的子数组 的 Lipschitz 常数为：

• 
• 
• 

该查询的答案即为上述 Lipschitz 常数之和。