#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e2+5;
int p[N],w[N],n,m,lst[N],nxt[N],to[N],mk[N];
int solve(int l,int r){
    if(l>r)return 0;
    for(int i=l;i<=r;i++)p[i]=w[i];
    int res=0;
    for(int i=l;i<=r;i++){
        int op=0;
        for(int j=i+1;j<=r;j++){
            if(p[i]<p[j])swap(p[i],p[j]),op=1;
        }
        res+=op==0;
    }
    return res;
}
int Solve(int l,int r){
    if(l>r)return 0;
    int res=0;
    memset(mk,0,sizeof(mk));
    for(int i=l;i<=r;i++){
        if(lst[i]>=l)continue;
        mk[w[i]]++;
        int op=mk[w[i]];
        for(int j=nxt[i];j<=r;j++)if(w[j]>w[i])op--;
        res+=op>0;
    }
    return res;
}
vector<int>q,st;
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];
    q.push_back(0);
    for(int i=1;i<=n;i++){
        while(w[q.back()]>=w[i])q.pop_back();
        lst[i]=q.back();
        q.push_back(i);
    }
    q.clear();
    q.push_back(n+1);st.push_back(n+1);
    for(int i=n;i>=1;i--){
        while(w[q.back()]>=w[i])q.pop_back();
        nxt[i]=q.back();
        q.push_back(i);
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<r-l+1-Solve(l,r)<<'\n';
    }
}