#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

#define N 500001

using namespace std;
int n,q,a[N],ans[N];
vector<int> vpos[N];

int c[N];

int lowbit(int x) { return x&-x; }
void upd(int x,int k) { for (int i=x;i<=n;i+=lowbit(i)) c[i]+=k; }
int ask(int x) { int res=0; for (int i=x;i;i-=lowbit(i)) res+=c[i]; return res; }

struct Q {
    int l,r,id;

    bool operator<(Q t) { return l^t.l?l<t.l:r>t.r; }
}_q[N];

struct Q1 { int l,r,tid; };
vector<Q1> st;

struct Tree2 {
    struct Tree { int val,tag; }t[N<<2];
    void pushdown(int x);
    void updf(int x,int l,int r,int pos,int k);
    void upd(int x,int l,int r,int L,int R,int k);
    void ask(int x,int l,int r,int k);
}t2;

struct Tree1 {
    struct Tree {
        int r,id;
    
        bool operator<(Tree tmp) { return r<tmp.r; }
    }t[N<<2];
    vector<Tree> v[N];

    Tree max(Tree t1,Tree t2) { return t1.r>t2.r?t1:t2; }

    void build(int x,int l,int r) {
        t[x].r=1e9;
        if (l==r) return;
        int mid=(l+r>>1);
        build(x<<1,l,mid); build(x<<1|1,mid+1,r);
    }

    void upd(int x,int l,int r,int pos,int R,int id) {
        if (l==r) return t[x]={R,id},void();
        int mid=(l+r>>1);
        if (pos<=mid) upd(x<<1,l,mid,pos,R,id);
        else upd(x<<1|1,mid+1,r,pos,R,id);
        t[x].r=min(t[x<<1].r,t[x<<1|1].r);
    }

    void ask(int x,int l,int r,int L,int R,int pos) {
        if (L<=l and r<=R) {
            if (l==r) {
                Q1 tmp=Q1{l,t[x].r,t[x].id};
                st.insert(lower_bound(st.begin(),st.end(),tmp,[](Q1 tmp1,Q1 tmp2) { return tmp1.l<tmp2.l; }),tmp);
                t2.updf(1,1,q,t[x].id,::ask(_q[t[x].id].r)-::ask(_q[t[x].id].l-1));
                if (v[l].empty()) t[x]={(int)1e9,(int)1e9};
                else t[x]=v[l].back(),v[l].pop_back();
                return;
            }
            int mid=(l+r>>1);
            if (t[x<<1].r<=pos) ask(x<<1,l,mid,L,R,pos);
            if (t[x<<1|1].r<=pos) ask(x<<1|1,mid+1,r,L,R,pos);
            t[x].r=min(t[x<<1].r,t[x<<1|1].r);
        }
        int mid=(l+r>>1);
        if (L<=mid and t[x<<1].r<=pos) ask(x<<1,l,mid,L,R,pos);
        if (R>mid and t[x<<1|1].r<=pos) ask(x<<1|1,mid+1,r,L,R,pos);
        t[x].r=min(t[x<<1].r,t[x<<1|1].r);
    }
}t1;

void Tree2::pushdown(int x) {
    if (t[x].tag) {
        t[x<<1].val+=t[x].tag,t[x<<1|1].val+=t[x].tag;
        t[x<<1].tag+=t[x].tag,t[x<<1|1].tag+=t[x].tag;
        t[x].tag=0;
    }
}

void Tree2::updf(int x,int l,int r,int pos,int k) {
    if (l==r) return t[x].val=k,void();
    int mid=(l+r>>1); pushdown(x);
    if (pos<=mid) updf(x<<1,l,mid,pos,k);
    else updf(x<<1|1,mid+1,r,pos,k);
    t[x].val=max(t[x<<1].val,t[x<<1|1].val);
}

void Tree2::upd(int x,int l,int r,int L,int R,int k) {
    if (L<=l and r<=R) return t[x].val+=k,t[x].tag+=k,void();
    int mid=(l+r>>1); pushdown(x);
    if (L<=mid) upd(x<<1,l,mid,L,R,k);
    if (R>mid) upd(x<<1|1,mid+1,r,L,R,k);
    t[x].val=max(t[x<<1].val,t[x<<1|1].val);
}

void Tree2::ask(int x,int l,int r,int k) {
    if (l==r) {
        ans[_q[l].id]=k,t[x].val=-1;
        Q1 tmp=Q1{_q[l].l,_q[l].r,l};
        st.erase(lower_bound(st.begin(),st.end(),tmp,[](Q1 tmp1,Q1 tmp2) { return tmp1.l<tmp2.l; }));
        t1.ask(1,1,n,_q[l].l,n,_q[l].r);
        return;
    }
    int mid=(l+r>>1); pushdown(x);
    if (t[x<<1].val>=k) ask(x<<1,l,mid,k);
    if (t[x<<1|1].val>=k) ask(x<<1|1,mid+1,r,k);
    t[x].val=max(t[x<<1].val,t[x<<1|1].val); 
}

int findl(int x) {
    int l=0,r=st.size()-1,res=-1;
    while (l<=r) {
        int mid=(l+r>>1);
        if (st[mid].r>=x) res=mid,r=mid-1;
        else l=mid+1;
    }
    return res;
}

int findr(int x) {
    int l=0,r=st.size()-1,res=-1;
    while (l<=r) {
        int mid=(l+r>>1);
        if (st[mid].l<=x) res=mid,l=mid+1;
        else r=mid-1;
    }
    return res;
}

int main() {
    scanf("%d%d",&n,&q); int maxn=5e5;
    for (int i=1;i<=n;i++) scanf("%d",a+i),maxn=max(maxn,a[i]),vpos[a[i]].push_back(i),upd(i,1);
    for (int i=1;i<=q;i++) scanf("%d%d",&_q[i].l,&_q[i].r),_q[i].id=i;
    sort(_q+1,_q+q+1);
    Q lst;
    t1.build(1,1,n);
    for (int i=1;i<=q;i++) {
        if (i==1 or _q[i].r>lst.r) {
            lst=_q[i],st.push_back({_q[i].l,_q[i].r,i});
            t2.updf(1,1,q,i,ask(_q[i].r)-ask(_q[i].l-1));
            // printf(" %d: %d\n",ask(_q[i].r)-ask(_q[i].l-1));
        } else {
            t1.v[_q[i].l].push_back({_q[i].r,i});
        }
    }
    for (int i=1;i<=n;i++) {
        sort(t1.v[i].begin(),t1.v[i].end());
        if (!t1.v[i].empty()) 
            t1.upd(1,1,n,i,t1.v[i].back().r,t1.v[i].back().id),t1.v[i].pop_back();
    }
    for (int i=maxn;i>=0;i--) { 
        for (int j:vpos[i]) {
            upd(j,-1);
            int l=findl(j),r=findr(j);
            if (l>r or l==-1 or r==-1) continue;
            // printf("1 %d: %d %d\n",i,st[l].tid,st[r].tid);
            l=st[l].tid,r=st[r].tid;
            t2.upd(1,1,q,l,r,-1);
        }
        t2.ask(1,1,q,i);
        // if (i<=3) {
        //     printf("2 %d: [%ld]",i,st.size());
        //     for (Q1 i:st) printf("(%d %d) ",i.l,i.r);
        //     printf("\n3: ");
        //     for (int j=1;j<=q;j++) printf("%d ",ans[j]);
        //     printf("\n\n");
        // }
    }
    for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}