90pts 求敲晕

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
int n,m,l,r,p=1,k;
int ans;
int f[N];
struct node{
    int val,pos;
}a[N];
struct yxt{
    int l,r,pos;
}d[N];
//询问
struct pre{
    int l,r;
}c[N];
//好对
bool cmp(node x,node y){
    return x.val<y.val;
}
bool cmp2(yxt x,yxt y){
    if(x.r!=y.r) return x.r<y.r;
    return x.l<y.l;
}bool cmp3(pre x,pre y){
    if(x.r!=y.r) return x.r<y.r;
    return x.l<y.l;
}
int lowbit(int x){return x&(-x);}
void add(int l,int r){
    c[++k].l=l;
    c[k].r=r;
}
void join(int x){
    while(x<=n){
        f[x]++;
        x+=lowbit(x);
    }
}
int ask(int x){
    int res=0;
    while(x){
        res+=f[x];
        x-=lowbit(x);
    }
    return res;
}
signed main(){
    cin>>n>>m;
    if(n==1){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++) cin>>a[i].val,a[i].pos=i;
    sort(a+1,a+1+n,cmp);
    add(min(a[1].pos,a[2].pos),max(a[1].pos,a[2].pos));
    add(min(a[n-1].pos,a[n].pos),max(a[n-1].pos,a[n].pos));
    for(int i=2;i<n;i++){
        if(a[i].val-a[i-1].val<a[i+1].val-a[i].val)
            add(min(a[i-1].pos,a[i].pos),max(a[i-1].pos,a[i].pos));
        else if(a[i].val-a[i-1].val>a[i+1].val-a[i].val)
            add(min(a[i+1].pos,a[i].pos),max(a[i+1].pos,a[i].pos));
        else{
            add(min(a[i-1].pos,a[i].pos),max(a[i-1].pos,a[i].pos));
            add(min(a[i+1].pos,a[i].pos),max(a[i+1].pos,a[i].pos));
        }
    }
    for(int i=1;i<=m;i++){
        cin>>d[i].l>>d[i].r;
        d[i].pos=i;
    }
    sort(c+1,c+1+k,cmp3);
    sort(d+1,d+1+m,cmp2);
    for(int i=1;i<=m;i++){
        while(p<=k&&c[p].r<=d[i].r){
            join(c[p].l);
            p++;
        }
        ans+=d[i].pos*(p-1-ask(d[i].l-1));
    }
    cout<<ans;
    return 0;
}
//sl:yxt~~