#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[500009],v[500009][4],fen[500009],ans[500009];
map <int, int> mp;
map <int, int>::iterator TA;
vector <pair <int, int> > V[500009];
void upd(int q, int w){
while(q<=500004){
fen[q]+=w;
q=q+(q&(-q));
}
}
int read(int q){
int sm=0;
while(q>0){
sm+=fen[q];
q=q-(q&(-q));
}
return sm;
}
void UPD(int q, int w, int rr){
upd(q,rr);upd(w+1,-rr);
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>tes;
for(i=1; i<=a; i++) cin>>f[i];
for(i=1; i<=a; i++){
mp[f[i]]=1;
}
zx=0;
for(TA=mp.begin(); TA!=mp.end(); TA++){
zx++;(*TA).second=zx;
}
for(i=1; i<=a; i++){
f[i]=mp[f[i]];
}
for(t=1; t<=tes; t++){
cin>>c>>d;
V[d].push_back({c,t});
}
for(i=1; i<=a; i++){
if(v[f[i]][0]!=0){
UPD(v[f[i]][1]+1,v[f[i]][0],1);
}
if(v[f[i]][1]!=0){
UPD(v[f[i]][2]+1,v[f[i]][1],-1);
}
for(vector <pair <int, int> >::iterator it=V[i].begin(); it!=V[i].end(); it++){
ans[(*it).second]=read((*it).first);
}
for(j=2; j>=1; j--){
v[f[i]][j]=v[f[i]][j-1];
}
v[f[i]][0]=i;
}
for(t=1; t<=tes; t++){
cout<<ans[t]<<"\n";
}
return 0;
}
