rt

#include<bits/stdc++.h>

const int N=500010,V=100010,M=710;

int n,m;
int a[N];

struct Query{
    int l,r,id;
}Q[N];
int block;
int get(int x){return (x-1)/block+1;}
bool cmp1(const Query &a,const Query &b){
    int al=get(a.l),bl=get(b.l);
    if(al!=bl)return al<bl;
    if(al&1)return a.r<b.r;
    return a.r>b.r;
}

int cnt[V];
long long sum[V],pre[N],suf[N];
int lowbit(int x){return x&-x;}
void adds(int x,int d){
    for(;x<=n;x+=lowbit(x))sum[x]+=d;
}
long long asks(int x){
    long long res=0;
    for(;x;x-=lowbit(x))res+=sum[x];
    return res;
}
void addc(int x,int d){
    for(;x<=n;x+=lowbit(x))cnt[x]+=d;
}
int askc(int x){
    int res=0;
    for(;x;x-=lowbit(x))res+=cnt[x];
    return res;
}

struct Sec{
    int l,r,t,id;
};
std::vector<Sec>rgpre[N],rgsuf[N];

int c1[N],c2[M];
long long s1[N],s2[M];

void add(int x){
    for(int i=1;i<get(x);++i)s2[i]+=x;
    for(int i=(get(x)-1)*block+1;i<=x;++i)s1[i]+=x;
    for(int i=get(x)+1;i<=get(n);++i)c2[i]+=1;
    for(int i=x;i<=std::min(get(x)*block,n);++i)c1[i]+=1;
}

long long calc(int x){
    return (s1[x+1]+s2[get(x)+1])+(long long)x*(c1[x-1]+c2[get(x)-1]);
}

long long ans[N];
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);

    std::cin>>n>>m;
    for(int i=1;i<=n;++i)std::cin>>a[i];
    for(int i=1;i<=m;++i)std::cin>>Q[i].l>>Q[i].r,Q[i].id=i;
    block=std::sqrt(n);
    std::sort(Q+1,Q+1+m,cmp1);

    long long Pre=0,Suf=0;
    for(int i=1;i<=n;++i){
        pre[i]=pre[i-1]+Pre-asks(a[i])+(long long)a[i]*(askc(a[i]-1)+1);
        adds(a[i],a[i]),addc(a[i],1),Pre+=a[i];
    }
    std::memset(sum,0,sizeof sum),std::memset(cnt,0,sizeof cnt);
    for(int i=n;i>=1;--i){
        suf[i]=suf[i+1]+Suf-asks(a[i])+(long long)a[i]*(askc(a[i]-1)+1);
        adds(a[i],a[i]),addc(a[i],1),Suf+=a[i];
    }

    for(int i=1,L=1,R=0;i<=m;++i){
        auto &[l,r,id]=Q[i];
        if(R<r)rgpre[L-1].emplace_back((Sec){R+1,r,-1,id}),ans[id]+=pre[r]-pre[R],R=r;
        if(R>r)rgpre[L-1].emplace_back((Sec){r+1,R, 1,id}),ans[id]-=pre[R]-pre[r],R=r;
        if(L<l)rgsuf[R+1].emplace_back((Sec){L,l-1, 1,id}),ans[id]-=suf[L]-suf[l],L=l;
        if(L>l)rgsuf[R+1].emplace_back((Sec){l,L-1,-1,id}),ans[id]+=suf[l]-suf[L],L=l;
    }

    for(int i=1;i<=n;++i){
        add(a[i]);
        for(auto &rg:rgpre[i]){
            int l=rg.l,r=rg.r,t=rg.t,id=rg.id;
            for(int x=l;x<=r;++x)ans[id]+=(long long)t*calc(a[x]);
        }
    }
    std::memset(c1,0,sizeof c1),std::memset(c2,0,sizeof c2);
    std::memset(s1,0,sizeof s1),std::memset(s2,0,sizeof s2);
    for(int i=n;i>=1;--i){
        add(a[i]);
        for(auto &rg:rgsuf[i]){
            int l=rg.l,r=rg.r,t=rg.t,id=rg.id;
            for(int x=l;x<=r;++x)ans[id]+=(long long)t*calc(a[x]);
        }
    }

    for(int i=1;i<=m;++i)ans[Q[i].id]+=ans[Q[i-1].id];
    for(int i=1;i<=m;++i)std::cout<<ans[i]<<'\n';

    return 0;
}