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 .

Input

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 $*l*_{*i*}$ and $*r*_{*i*}$ ($1 ≤ *l*_{*i*} < *r*_{*i*} ≤ *n*$).

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 .

Note

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.