#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=200000+100;
int bit[maxn];
int ans[maxn];
int Ans[maxn];
int n,m;
inline int lowbit(int x){
return x&(-x);
}
inline void Add(int x,int v){
while(x<=n){
bit[x]+=v;
x+=lowbit(x);
}
}
inline int getSum(int x){
int sum=0;
while(x>0){
sum+=bit[x];
x-=lowbit(x);
}
return sum;
}
struct Query{
int l,r;
int id;
}query[maxn];
inline bool cmp(Query a,Query b){
return a.r<b.r;
}
int main(){
map<int,int>M;
while(scanf("%d%d",&n,&m)==2){
M.clear();
for(int i=1;i<=n;i++) scanf("%d",&ans[i]),ans[n+i]=ans[i],bit[i]=bit[n+i]=0;
for(int i=1;i<=m;i++){
scanf("%d%d",&query[i].r,&query[i].l);
query[i].r+=n;
query[i].id=i;
}
n*=2;
sort(query+1,query+m+1,cmp);
int pre=1;
for(int i=1;i<=m;i++){
for(int j=pre;j<=query[i].r;j++){
if(M[ans[j]]!=0) Add(M[ans[j]],-1);
Add(j,1);
M[ans[j]]=j;
}
pre=query[i].r+1;
Ans[query[i].id]=getSum(query[i].r)-getSum(query[i].l-1);
}
for(int i=1;i<=m;i++) printf("%d\n",Ans[i]);
}
}
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+100;
struct Tree{
int l,r;
int sum;
}tree[maxn*40];
int Root[maxn];
int num[maxn];
int ans[maxn];
int tot;
int n,m;
inline void build(int &New,int l,int r){
New=++tot;
tree[New].l=0;
tree[New].r=0;
tree[New].sum=0;
if(l==r) return;
int mid=(l+r)>>1;
build(tree[New].l,l,mid);
build(tree[New].r,mid+1,r);
}
inline void update(int l,int r,int &New,int Old,int ind,int v){
New=++tot;
tree[New]=tree[Old];
if(l==r){
tree[New].sum+=v;
return ;
}
int mid=(l+r)>>1;
if(mid>=ind) update(l,mid,tree[New].l,tree[Old].l,ind,v);
else update(mid+1,r,tree[New].r,tree[Old].r,ind,v);
tree[New].sum=tree[tree[New].l].sum+tree[tree[New].r].sum;
}
inline int query(int l,int r,int L,int R,int ind){
if(L<=l && R>=r) return tree[ind].sum;
int mid=(l+r)>>1;
if(mid>=R) return query(l,mid,L,R,tree[ind].l);
else if(L>mid) return query(mid+1,r,L,R,tree[ind].r);
else return query(l,mid,L,R,tree[ind].l)+query(mid+1,r,L,R,tree[ind].r);
}
inline void scan_d(int &res){
res=0;
char ch;
ch=getchar();
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9') res=res*10+(ch-'0'),ch=getchar();
}
inline void print_d(int res){
if(res>9) print_d(res/10);
putchar(res%10+'0');
}
int main(){
while(scanf("%d%d",&n,&m)==2){
if(!n) break;
tot=0;
for(int i=1;i<=n;i++) scan_d(ans[i]),ans[i+n]=ans[i],num[ans[i]]=-1;
n*=2;
build(Root[0],1,n);
for(int i=1;i<=n;i++){
if(num[ans[i]]==-1){
update(1,n,Root[i],Root[i-1],i,1);
num[ans[i]]=i;
}
else{
int tmp;
update(1,n,tmp,Root[i-1],num[ans[i]],-1);
update(1,n,Root[i],tmp,i,1);
num[ans[i]]=i;
}
}
for(int i=1;i<=m;i++){
int l,r;
scan_d(r);
scan_d(l);
r+=n/2;
print_d(query(1,n,l,r,Root[r])),putchar('\n');
}
}
}
