遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办m次车展。车库里共有n辆车，从左到右依次编号为1，2，…，n，每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子：
L1 R1
L2 R2
…
Lm Rm
单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车。

为了更加美观，展览时需要调整展台的高度，使参展所有展台的高度相等。展台的高度增加或减少1都需花费1秒时间。由于管理员只有一个人，所以只好对每个展台依次操作。每次展览结束后，展台高度自动恢复到初始高度。

请告诉管理员为了举办所有展览，他最少需要花多少时间将展台调整好。

输入格式

输出格式

样例输入1[复制]

6 4

4 1 2 13 0 9

1 5

2 6

3 4

2 2

样例输出1[复制]

48

各个测试点1s

对于50％的数据 n≤500，m≤1000；
对于80％的数据 n≤1000，m≤100000；
对于100％的数据n≤1000，m≤200000；
答案在2^64以内。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int N = 1e5+, M = 1e3+, MOD = 1e9+, inf = 2e9;

typedef long long ll;

struct data{int l,r,v,size,rnd,w;ll sum;}tr[N * ];

int n,siz ,m, a[N],root, ans[M][M] ,Sum,cnt,snt;

void update(int k) {

    tr[k].size = tr[tr[k].l].size+tr[tr[k].r].size + tr[k].w;

    tr[k].sum = tr[tr[k].l].sum + tr[tr[k].r].sum + tr[k].w*tr[k].v;

}

void lturn(int &k) {

    int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;update(k);update(t);k=t;

}

void rturn(int &k) {

    int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;update(k);update(t);k=t;

}

void insert(int &k,int x) {

    if(!k) {

        k=++siz;

        tr[k].w=tr[k].size=;

        tr[k].v=tr[k].sum=x;

        tr[k].rnd = rand();

        tr[k].l = tr[k].r =;

        return ;

    }

    tr[k].size++;tr[k].sum+=x;

    if(tr[k].v==x) tr[k].w++;

    else if(x>tr[k].v) {

        insert(tr[k].r,x);

        if(tr[tr[k].r].rnd<tr[k].rnd) lturn(k);

    }else {

        insert(tr[k].l,x);

        if(tr[tr[k].l].rnd<tr[k].rnd) rturn(k);

    }

}

int query(int k,int x) {

    if(x<=tr[tr[k].l].size) return query(tr[k].l,x);

    else if(x>tr[tr[k].l].size + tr[k].w) {

        cnt+=tr[tr[k].l].size + tr[k].w;

        snt+=tr[tr[k].l].sum+tr[k].w*tr[k].v;

        return query(tr[k].r,x - tr[tr[k].l].size - tr[k].w);

    }else {

        cnt+=tr[tr[k].l].size;

        snt+=tr[tr[k].l].sum;

        return tr[k].v;

    }

}

int main() {

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    for(int i=;i<=n;i++) {

        root = siz = ;

        Sum = ;

        for(int j=i;j<=n;j++) {

            Sum += a[j];

            insert(root,a[j]);

            cnt = snt = ;

            int ave = query(root,(j-i+) / );

            ans[i][j] = cnt*ave - snt + Sum - snt - (j-i+-cnt)*ave;

        }

    }

    ll all = ;

    while(m--) {

        int l,r;

        scanf("%d%d",&l,&r);

        all+=ans[l][r];

    }

    cout<<all<<endl;

}