#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
inline int read(){
    int res=0,in=getchar(),sign=1;
    while(in<'0'||in>'9'){if(in=='-')sign=-1;in=getchar();}
    while(in>='0'&&in<='9')res=(res<<1)+(res<<3)+(in^48),in=getchar();
    return res*sign;
}
void print(int num){
    if(num>9)print(num/10);
    putchar((signed)(num%10)+'0');
}
const int N=1000100,M=250100;
struct bta{
    int t[M];
    void init(){memset(t,0,sizeof(t));}
    void add(int id,int k){while(id<M)t[id]+=k,id+=(id&-id);}
    int get_(int id){int res=0;while(id)res+=t[id],id-=(id&-id);return res;}
};
struct blk{
    int bel[M],laz[M],a[M],siz;
    void init(){siz=711;for(int i=1;i<M;i++)bel[i]=(i-1)/siz+1,laz[i]=a[i]=0; }
    void add(int l,int r,int k){
        for(int i=l,end=min(bel[l]*siz,r);i<=end;i++)a[i]+=k;
        if(bel[l]!=bel[r])for(int i=bel[r]*siz-siz+1;i<=r;i++)a[i]+=k;
        for(int i=bel[l]+1;i<bel[r];i++)laz[i]+=k;
    }
    int get_(int id){return a[id]+laz[bel[id]];}
};
int n,m,lp=1,rp,fl[N],fg[N],bel[N],a[N],res[N];
struct offline{
    int l,r,id,ans;
    bool operator<(const offline&b)const&{
        if(bel[l]==bel[b.l])
            if(bel[l]&1)return r>b.r;
            else return r<b.r;
        else return bel[l]<bel[b.l];
    }
}ask[N];
struct of2{
    int l,r,sign,id,is_r;
};
vector<of2>t[N];
void init(){
    n=read();m=read();
    int siz=(int)sqrt(n);
    bta b1;
    bta b2;
    b1.init();
    b2.init();
    for(int i=1;i<=n;i++){
        a[i]=read();
        bel[i]=(i-1)/siz;
        fl[i]=b1.get_(a[i]-1);
        fg[i]=b2.get_(M-1)-b2.get_(a[i]);
        b1.add(a[i],1);
        b2.add(a[i],a[i]);
    }
    for(int i=1;i<=m;i++)ask[i]={read(),read(),i,0};
    sort(ask+1,ask+m+1);
}
signed main(){
    init();
    for(int i=1;i<=m;i++){
        int L=ask[i].l,R=ask[i].r;
        if(rp<R)t[lp-1].emplace_back((of2){rp+1,R,-1,i,1});
        if(rp>R)t[lp-1].emplace_back((of2){R+1,rp,1,i,1});
        while(rp<R)rp++,ask[i].ans+=(fl[rp]+1)*a[rp]+fg[rp];
        while(rp>R)ask[i].ans-=(fl[rp]+1)*a[rp]+fg[rp],rp--;
        if(lp>L)t[rp].emplace_back((of2){L,lp-1,1,i,0});
        if(lp<L)t[rp].emplace_back((of2){lp,L-1,-1,i,0});
        while(lp>L)lp--,ask[i].ans-=fl[lp]*a[lp]+fg[lp];
        while(lp<L)ask[i].ans+=fl[lp]*a[lp]+fg[lp],lp++;
    }
    blk b1;blk b2;
    b1.init();b2.init();
    for(int i=1;i<=n;i++){
        b1.add(a[i]+1,M-1,1);
        b2.add(1,a[i]-1,a[i]);
        for(int j=0;j<t[i].size();j++)
            for(int k=t[i][j].l;k<=t[i][j].r;k++)
                if(t[i][j].is_r)ask[t[i][j].id].ans+=t[i][j].sign*(b1.get_(a[k])*a[k]+b2.get_(a[k]));
                else ask[t[i][j].id].ans+=t[i][j].sign*((b1.get_(a[k])+1)*a[k]+b2.get_(a[k]));
    }
    for(int i=1;i<=m;i++)ask[i].ans+=ask[i-1].ans,res[ask[i].id]=ask[i].ans;
    for(int i=1;i<=m;i++)print(res[i]),putchar('\n');
    return 0;
}

断断续续调了一周QAQ