2586.Lipshitz Sequence
Time Limit: 1s Memory Limit: 256MBA function 
is called Lipschitz continuous if there is a real constant K such that the inequality |f(x)-f(y)| \le K \cdot |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 \lt 2, 
if n \ge 2, 
over all 1 \le i \lt j \le n In other words, 
is the smallest non-negative integer such that |h[i]-h[j]| \le L \cdot |i-j| holds for all 1 \le i,j \le 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 
.
Input Format(From the terminal/stdin)
Input The first line of the input contains two space-separated integers n and q (2 \le n \le 100000 and 1 \le q \le 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 \le li \lt ri \le n).
Output Format(To the terminal/stdout)
Output 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 
.
Sample Input 1
10 4 1 5 2 9 1 3 4 2 1 7 2 4 3 8 7 10 1 9· \n · · · · · · · · · \n · \n · \n · \n · \n
Sample Output 1
17 82 23 210\n \n \n \n
Sample Input 2
7 6 5 7 7 4 6 6 2 1 2 2 3 2 6 1 7 4 7 3 5· \n · · · · · · \n · \n · \n · \n · \n · \n · \n
Sample Output 2
2 0 22 59 16 8\n \n \n \n \n \n
Hints
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.