#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

inline char gc() { // like getchar()
	static char buf[1 << 16];
	static size_t bc, be;
	if (bc >= be) {
		buf[0] = 0, bc = 0;
		be = fread(buf, 1, sizeof(buf), stdin);
	}
	return buf[bc++]; // returns 0 on EOF
}

int readInt() {
	int a, c;
	while ((a = gc()) < 40);
	if (a == '-') return -readInt();
	while ((c = gc()) >= 48) a = a * 10 + c - 480;
	return a - 48;
}


const int maxn=3e5+10;



int n,q,a[maxn];
vector<int>vect[maxn],g[maxn],opens[maxn],closes[maxn],cand[maxn];
vector<pii>qrys[maxn];
int pos[maxn],nstart[maxn],nend[maxn],ctm,rez[maxn];

int tree[maxn*4];

void dfs(int x){
    nstart[x]=++ctm;
    for(int i=0;i<g[x].size();i++){
        int id=g[x][i];
        dfs(id);
    }
    nend[x]=ctm;
}
void prek(){

    vector<pii>events;

    for(int i=1;i<=n;i++){
        int sz=vect[i].size();
        for(int j=sz-2;j>0;j--){
            opens[vect[i][j-1]+1].pb(vect[i][j+1]);
            closes[vect[i][j]+1].pb(vect[i][j+1]);
        }
    }

    multiset<int>st;
    for(int i=1;i<=n;i++){
        for(int j=0;j<opens[i].size();j++)
            st.insert(opens[i][j]);
        for(int j=0;j<closes[i].size();j++)
            st.erase(st.find(closes[i][j]));

        int x=n+1;
        if(st.size())x=(*st.begin());
        pos[i]=x;
        cand[pos[i]].pb(i);
        pos[i]++;
        pos[i]=min(pos[i],n+1);

        g[pos[i]].pb(i);

        ///printf("%d ",x);
    }
    ///printf(" POS\n");

    dfs(n+1);

}

void push(int x){
    if(tree[x]==0)return;
    tree[x*2]+=tree[x];
    tree[1+x*2]+=tree[x];
    tree[x]=0;
}
int qry(int x,int l,int r,int id){
    if(l==r)return tree[x];
    push(x);
    int mid=(l+r)/2;
    if(id<=mid)return qry(x*2,l,mid,id);
    else return qry(x*2+1,mid+1,r,id);
}
void upd(int x,int l,int r,int lp,int rp,int val){

    if(l>rp || r<lp)return;
    if(l>=lp && r<=rp){
        tree[x]+=val;
        return;
    }
    push(x);
    int mid=(l+r)/2;

    upd(x*2,l,mid,lp,rp,val);
    upd(x*2+1,mid+1,r,lp,rp,val);
}

int main(){

    freopen("matchingseq.in","r",stdin);
    freopen("matchingseq.out","w",stdout);

    n=readInt();
    q=readInt();
    for(int i=1;i<=n;i++)vect[i].pb(0);
    for(int i=1;i<=n;i++){
        a[i]=readInt();
        vect[a[i]].pb(i);
    }

    prek();

    for(int i=1;i<=q;i++){
        int l,r;
        l=readInt();
        r=readInt();
        qrys[r].pb({l,i});
    }

    for(int i=1;i<=n;i++){

        for(int j=0;j<cand[i].size();j++){
            int id=cand[i][j];
            upd(1,1,ctm,nstart[id],nend[id],1);
        }

        for(int j=0;j<qrys[i].size();j++){
            int id=qrys[i][j].ss;
            int lp=qrys[i][j].ff;

            rez[id]=qry(1,1,ctm,nstart[lp]);
        }

    }

    for(int i=1;i<=q;i++){
        printf("%d\n",rez[i]);
    }

    return 0;
}