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 .

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.