#include <bits/stdc++.h>
using namespace std;

using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n)  for(int i=0;i<(n);++i)
#define sizc(x) ((int)x.size())
#define allc(x) x.begin(),x.end()
#define fir first
#define sec second

char getc(){
    constexpr int SZ=1<<14;
    static char buf[SZ],*p=buf,*q=buf;
    if(p==q){
        p=buf;
        q=buf+fread(buf,1,SZ,stdin);
        if(p==q)return EOF;
    }
    return *p++;
}
int read(){
    int x=0,sg=0;
    char ch=getc();
    while(!isdigit(ch))sg|=ch=='-',ch=getc();
    while(isdigit(ch))x=x*10+(ch-'0'),ch=getc();
    return sg?-x:x;
}


constexpr int N = 2e6+5;

int n,m;
int a[N];
int p[N];

struct query{
    int l,r,id;
}q[N],tq[N];
ll ans[N];

int pre[N],nxt[N],vl[N];

struct segtree{
    ll c[N<<1];
    void add(int x,ll y){
        x+=n-1;
        while(x)c[x]+=y,x>>=4;
    }
    ll sum(int x){
        int l=n,r=n+x-1;
        ll ret=0;
        while((l>>4)!=(r>>4)){
            while(l&15)ret+=c[l++];
            while(r+1&15)ret+=c[r--];
            l>>=4,r>>=4;
        }
        return accumulate(c+l,c+r+1,ret);
    }
}sgt;

void dc(int l,int r,int ql,int qr){
    if(ql>qr||l==r){
        sort(p+l,p+r+1,[&](int x,int y){
            return a[x]<a[y];
        });
        return;
    }
    int mid=l+r>>1;
    int p1=partition(q+ql,q+qr+1,[&](const query &a){
        return a.r<=mid;
    })-q;
    int p2=partition(q+p1,q+qr+1,[&](const query &a){
        return a.l>mid;
    })-q;
    dc(l,mid,ql,p1-1),dc(mid+1,r,p1,p2-1);

    sort(q+p2,q+qr+1,[&](const query &a,const query &b){
        return a.r>b.r;
    });
    int ptr=l;
    ll sum=0;
    rep(i,mid,r){
        int x=i>mid?p[i]:0,y=i<r?p[i+1]:n+1;
        nxt[x]=y,pre[y]=x;
        vl[x]=0;
        while(ptr<=mid&&a[p[ptr]]<a[y])vl[x]=max(vl[x],p[ptr++]);
        int v1=x+(y>n?0:y),v2=x>0&&y<=n?abs(x-y):0;
        sum+=v1,sgt.add(vl[x]+1,v2-v1);
    }
    ptr=p2;
    per(i,r,mid+1){
        while(ptr<=qr&&q[ptr].r==i){
            ans[q[ptr].id]+=sum+sgt.sum(q[ptr].l);
            ++ptr;
        }
        int x=pre[i],y=nxt[i];
        int v1=x+i,v2=x>0?i-x:0;
        sum-=v1,sgt.add(vl[x]+1,v1-v2);
        v1=i+(y>n?0:y),v2=y<=n?i-y:0;
        sum-=v1,sgt.add(vl[i]+1,v1-v2);
        vl[x]=max(vl[x],vl[i]);
        v1=x+(y>n?0:y),v2=x>0&&y<=n?abs(x-y):0;
        sum+=v1,sgt.add(vl[x]+1,v2-v1);
        nxt[x]=y,pre[y]=x;
    }

    sort(q+p2,q+qr+1,[&](const query &a,const query &b){
        return a.l<b.l;
    });
    ptr=mid+1,sum=0;
    rep(i,l-1,mid){
        int x=i<l?0:p[i],y=i<mid?p[i+1]:n+1;
        nxt[x]=y,pre[y]=x;
        vl[x]=n+1;
        while(ptr<=r&&a[p[ptr]]<a[y])vl[x]=min(vl[x],p[ptr++]);
        int v1=-x-(y>n?0:y),v2=x>0&&y<=n?abs(x-y):0;
        sum+=v2,sgt.add(vl[x],v1-v2);
    }
    ptr=p2;
    rep(i,l,mid){
        while(ptr<=qr&&q[ptr].l==i){
            ans[q[ptr].id]+=sum+sgt.sum(q[ptr].r);
            ++ptr;
        }
        int x=pre[i],y=nxt[i];
        int v1=-x-i,v2=x>0?x-i:0;
        sum-=v2,sgt.add(vl[x],v2-v1);
        v1=-i-(y>n?0:y),v2=y<=n?y-i:0;
        sum-=v2,sgt.add(vl[i],v2-v1);
        vl[x]=min(vl[x],vl[i]);
        v1=-x-(y>n?0:y),v2=x>0&&y<=n?abs(x-y):0;
        sum+=v2,sgt.add(vl[x],v1-v2);
        nxt[x]=y,pre[y]=x;
    }

    inplace_merge(p+l,p+mid+1,p+r+1,[&](int x,int y){
        return a[x]<a[y];
    });
}

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    n=read(),m=read();
    rep(i,1,n)a[i]=read(),p[i]=i;a[n+1]=n+1;
    rep(i,1,m)q[i].l=read(),q[i].r=read(),q[i].id=i;
    dc(1,n,1,m);rep(i,1,m)cout<<ans[i]<<'\n';
}