#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int p[N],w[N],n,m,lst[N],nxt[N],lth[N],mk[N],wz[N],to[N],rs[N],c[N],idx,hd[N];
void add(int x,int sm){
    while(x<=n){
        c[x]+=sm;
        x+=x&-x;
    }
}
int gets(int x){
    int res=0;
    while(x){
        res+=c[x];
        x-=x&-x;
    }
    return res;
}
void add(int l,int r,int sm){
    add(l,sm);add(r+1,-sm);
}
vector<int>st,f[N];
vector<pair<int,int> >g[N];
struct node{
    int bh,dy;
    friend bool operator<(node a,node b){
        if(a.bh==b.bh)return a.dy<b.dy;
        return a.bh<b.bh;
    }
};
set<node>q;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    st.push_back(0);
    for(int i=1;i<=n;i++){
        while(w[st.back()]>=w[i])st.pop_back();
        lst[i]=st.back();
        st.push_back(i);
    }
    st.clear();
    st.push_back(n+1);
    for(int i=n;i>=1;i--){
        while(w[st.back()]>=w[i])st.pop_back();
        nxt[i]=st.back();
        st.push_back(i);
    }
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        g[r].push_back({l,i});
        rs[i]=r-l+1;
    }
    for(int i=1;i<=n;i++){
        if(wz[w[i]]<=lst[i]){
            q.insert({w[i],++idx});
            hd[w[i]]=idx;
            f[idx].push_back(i);
            add(lst[i]+1,i,1);
        }else{
            int c=hd[w[i]];
            f[c].push_back(i);
            add(lst[i]+1,i,1);
        }
        for(auto j:q){
            if(j.bh>=w[i])break;
            if(!f[j.dy].size())continue;
            int c=f[j.dy].back();
            if(nxt[c]>i)continue;
            add(lst[c]+1,c,-1);
            f[j.dy].pop_back();
        }
        wz[w[i]]=i;
        for(auto j:g[i]){
            rs[j.second]-=gets(j.first);
        }
    }
    for(int i=1;i<=m;i++)cout<<rs[i]<<"\n";
}