| Codeforces Round 333 (Div. 1) |
|---|
| Finished |
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 
.
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 li and ri (1 ≤ li < ri ≤ 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 
.
10 4
1 5 2 9 1 3 4 2 1 7
2 4
3 8
7 10
1 9
17
82
23
210
7 6
5 7 7 4 6 6 2
1 2
2 3
2 6
1 7
4 7
3 5
2
0
22
59
16
8
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.
