time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

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 li and ri (1 ≤ li < ri ≤ 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 .

Examples

input

10 4

1 5 2 9 1 3 4 2 1 7

2 4

3 8

7 10

1 9

output

17

82

23

210

input

7 6

5 7 7 4 6 6 2

1 2

2 3

2 6

1 7

4 7

3 5

output

2

0

22

59

16

8

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.

【题目链接】:http://codeforces.com/contest/602/problem/D

【题解】



题意:

给你n个数字;

然后给你q个区间

每个区间l,r

让你求出[l,r]这个区间里面的数字的所有子列的L(h)的值的和;

(L(h)是任意两个点的斜率的绝对值的最大值);

做法:

可以肯定让你求L..R这个子列的区间的L(h)值

L(h)值必然是在abs(a[i]-a[i-1])中取到(i∈【L..R-1】)

可以看下图;



假设斜率的最大值不在相邻的两点之间得到;

设中间还有一个k;

则如果ak大于ai，则ai,ak连起来肯定更优,肯定比ai,aj连起来的斜率大

如果ak小于ai的话，则是ak,aj连起来更优;

总之只有在i,j相邻的时候,斜率才可能取到最大;

这样的话,我们就先把L..R这个区间内的相邻的数的差的绝对值处理出来

变为bi数组

然后枚举第bi中的第i个数字为斜率的最大值

看看这第i个数字能够“管理”“统治”的区间范围;

然后这段区间里面只要包括这第i个数字,则最大值肯定是就是第i个数字;

设其左边有l[i]个数字，右边有r[i]个数字

则答案递增l[i]*r[i]*b[i];

(左边选取l[i]个数字中的一个作为左端点,右边选取r[i]中的一个数字作为右端点,两个点组合成一个包围第i个点的区间);

这种问题可以用单调队列来搞;(单调栈?)

但是要注意重复的问题,所以左边在判断的时候加等号

右边判断的时候不加等号;

这样就不会重复计数了;

(可以拿样例中的第二组询问来理解这个重复区间的问题);



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%I64d",&x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int MAXN = 1e5+10;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

int n,q,top;

LL l[MAXN],r[MAXN],b[MAXN],a[MAXN];

int s[MAXN];

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    rei(n);rei(q);

    rep1(i,1,n)

        rel(a[i]);

    rep1(i,1,q)

    {

        LL L,R,len,ans = 0;

        rel(L);rel(R);

        len = R-L;

        rep1(j,L,R-1)

            b[j-L+1] = abs(a[j+1]-a[j]);

        //j∈L..R-1

        top=0;

        for (LL j = 1;j <= len;j++)

        {

            while (top && b[j]>=b[s[top]]) top--;//加等号

            if (top==0)

                l[j] = 0;

            else

                l[j] = s[top];

            //s[top]>b[j]

            s[++top] = j;

        }

        top = 0;

        for (LL j = len;j >=1 ;j--)

        {

            while (top && b[j]>b[s[top]]) top--;//不加等号

            if (top==0)

                r[j] = len+1;

            else

                r[j] = s[top];

            //s[top]>b[j]

            s[++top] = j;

        }

        for (LL j = 1;j <= len;j++)

             ans+=(j-l[j])*(r[j]-j)*b[j];

        cout << ans << endl;

    }

    return 0;

}