///O(N*sqrt(N))
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,v[200002],box[502],kb,ks,kd,kps,kpd,Lbox,Nbox,m,p,q,val,x,y,i,j,l;
long long putere[200002];
int main(){
    FILE *fin,*fout;
    fin= fopen("secvcost.in","rt");
    fout=fopen("secvcost.out","wt");
    fscanf(fin,"%d %d",&n,&m);
    for(i=1;i<=n;i++){
        fscanf(fin,"%d",v+i);
    }
    Lbox=500;///lungimea cutiilor
    Nbox=(n-1)/Lbox+1;///nr cutiei ce contine pozitia n; implicit ultima cutie
    ///initial box[i] este zero
    ///vom calcula maximul din fiecare cutie si pozitia acestuia (care este unica)
    for(i=1;i<=n;i++){
        kb=(i-1)/Lbox+1;///nr cutiei ce contine pozitia i;
        if(v[i]>box[kb]){
            box[kb]=v[i];
        }
    }
    for(i=1;i<=n;i++){
        kb=(i-1)/Lbox+1;///cutia kb contine pozitia i
        ///caut extrema stanga pentru puterea v[i]
        ///in cutia curenta kb
        ks=(kb-1)*Lbox+1;///capatul stang al cutiei kb
        ///parcurg descrescator secventa [ks;i-1]
        j=i-1;
        while(j>=ks && v[j]<=v[i]){
            j--;
        }
        ///sau j este in afara cutiei kb sau v[j] este mai puternic decat v[i]
        kps=j+1;///pastrez in kps pozitia care ar putea fi extrema cautata
        ///dar totusi verific si spre stanga
        if(j<ks){///trebuie sa mai caut spre stanga
            ///caut in cutiile din stanga
            j=kb-1;
            while(j>=1 && box[j]<=v[i]){
                j--;
            }
            ///avem cazul 1 (j==0); sau cazul 2, (j>=1 si box[j]) si box[j] contine valoare mai puternica decat v[i]
            if(j==0)kps=1;
            else{
                ///suntem la cutia j; [(j-1)*Lbox+1;j*Lbox]
                l=j*Lbox;
                while(v[l]<=v[i]){
                    l--;
                }
                ///v[l] este mai puternic decat v[i]
                kps=l+1;
            }
        }
        ///cauta extrema dreapta
        kd=min(n,kb*Lbox);///extrema dreapta a cutiei curente kb poate depasi n
        ///cautam mai intai in [i+1;kd]
        j=i+1;
        while(j<=kd && v[j]<=v[i]){
            j++;
        }
        ///daca j<=kd atunci a gasit mai puternic decat v[i] chiar in cutia kb
        kpd=j-1;
        ///daca j>kd, atunci mai trebuie cautat cel mai puternic decat v[i]
        if(j>kd){///depasesc cutia curenta
            ///caut in cutiile din dreapta
            j=kb+1;
            while(j<=Nbox && box[j]<=v[i]){
                j++;
            }
            if(j>Nbox)kpd=n;///puterea lui v[i] depaseste n
            if(j<=Nbox){///mai trebuie cautat cel care limiteaza puterea lui v[i] in cutia j
                ///suntem la cutia j; [(j-1)*Lbox+1;min(n,j*Lbox)]; cautam pornind de la capatul stang
                l=(j-1)*Lbox+1;
                while(v[l]<=v[i]){
                    l++;
                }
                ///v[l] este mai puternic decat v[i]
                kpd=l-1;

            }
        }
        putere[i]=(long long)v[i]*(kpd-kps+1);
    }
    for(i=1;i<=n;i++){
        putere[i]=putere[i-1]+putere[i];
    }
    for(i=1;i<=m;i++){
        fscanf(fin,"%d %d",&x,&y);
        fprintf(fout,"%lld\n",putere[y]-putere[x-1]);
    }
    fclose(fin); fclose(fout);
    return 0;
}
