A10121. 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 .

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 $l_{i}$ and $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 .

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.