2196: Lipshitz Sequence
Time Limit: 2 Sec Memory Limit: 256 MBSubmit: 0 Solved: 0
[Submit] [Status] [Web Board] [Creator:]
Description
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≤100000 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.