#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int MAX=500005;
struct ST{
int s,e,m;
vector<int> A;
ST *l,*r;
ST(int s,int e,int* B){
this->s=s;
this->e=e;
m=(s+e)>>1;
if (s==e){
A.push_back(B[s]);
return;
}
l=new ST(s,m,B);
r=new ST(m+1,e,B);
A.resize(l->A.size()+r->A.size());
merge(l->A.begin(),l->A.end(),r->A.begin(),r->A.end(),A.begin());
}
int qry(int x,int y,int a){
if (x<=s&&y>=e){
//cout<<A.end()-upper_bound(A.begin(),A.end(),a)<<'\n';
return A.end()-upper_bound(A.begin(),A.end(),a);
}
if (y<s||x>e) return 0;
return l->qry(x,y,a)+r->qry(x,y,a);
}
};
int N,Q;
int A[MAX];
int B1[MAX],B2[MAX],B3[MAX];
map<int,int> m1;
map<int,int> m2;
map<int,int> m3;
int main(){
ios::sync_with_stdio(false);cin.tie(NULL);
cin>>N>>Q;
for (int i=0;i<N;i++) cin>>A[i];
for (int i=N-1;i>=0;i--){
B1[i]=m1.find(A[i])==m1.end()?1<<30:m1[A[i]];
B2[i]=m2.find(A[i])==m2.end()?1<<30:m2[A[i]];
B3[i]=m3.find(A[i])==m3.end()?1<<30:m3[A[i]];
if (m2.find(A[i])!=m2.end()) m3[A[i]]=m2[A[i]];
if (m1.find(A[i])!=m1.end()) m2[A[i]]=m1[A[i]];
m1[A[i]]=i;
}
auto st1=new ST(0,N-1,B1),st2=new ST(0,N-1,B2),st3=new ST(0,N-1,B3);
while (Q--){
int l,r;cin>>l>>r;l--,r--;
cout<<2*st2->qry(l,r,r)-st1->qry(l,r,r)-st3->qry(l,r,r)<<'\n';
}/**/
/*
for (int i=0;i<N;i++) cout<<B1[i]<<' ';cout<<'\n';
for (int i=0;i<N;i++) cout<<B2[i]<<' ';cout<<'\n';
for (int i=0;i<N;i++) cout<<B3[i]<<' ';cout<<'\n';
*/
}
