#include<bits/stdc++.h>

#define maxn 300005
#define int long long
#define INF 1e18
#define pii pair<int,int>

using namespace std;

inline long long read(){
	long long lre=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		lre=(lre<<3)+(lre<<1)+(c-'0');
		c=getchar();
	}
	return lre*f;
}

struct edge{
	int head[maxn],to[2*maxn],next[2*maxn],val[2*maxn];
	int e_cnt=1;
	void add(int u,int v,int w){
		to[e_cnt]=v;
		val[e_cnt]=w;
		next[e_cnt]=head[u];
		head[u]=e_cnt++;
	}
	void show(int n){
		cout<<"show"<<endl;
		for(int x=1;x<=n;x++){
			for(int i=head[x];i;i=next[i]){
				printf("%d %d\n",x,to[i]);
			}
		}
		cout<<"end"<<endl;
	}
}E,aE;//边和反边 

int n,q,res;
int a[maxn],lst[maxn];
vector<pii> vec;
int ind[maxn];
int f[21][maxn],depth[maxn];
int nxt[maxn];

void dfs(int x,edge *e){
	for(int i=1;i<=19;i++){
		f[i][x]=f[i-1][f[i-1][x]];
	}
//	cout<<"x="<<x<<" f:";
//	for(int i=0;i<2;i++){
	//	cout<<f[i][x]<<" ";
//	}
//	cout<<endl;
	for(int i=e->head[x];i;i=e->next[i]){
		int v=e->to[i],w=e->val[i];
		depth[v]=depth[x]+w;
		f[0][v]=x;
		dfs(v,e);
	}
}

signed main(){
	
	n=read();q=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(lst[a[i]]){
			vec.push_back(make_pair(lst[a[i]],i));
		//	cout<<"range ["<<lst[a[i]]<<","<<i<<"]"<<endl;
			ind[vec.size()-1]=vec.size()-1;
		}
		lst[a[i]]=i;
	}
	//对于每一个区间[l1,r1],找到r1<l2中r2最小的点并连边
	//vec按照右端点排序的,ind按照左端点排序
	sort(ind,ind+vec.size(),[&](int a,int b){
		return vec[a].first<vec[b].first;	
	});
//	cout<<"show vec:";
//	for(pii p:vec)cout<<"("<<p.first<<","<<p.second<<")";
//	cout<<endl;
//	cout<<"show ind:";
//	for(int i=0;i<vec.size();++i)cout<<"("<<vec[ind[i]].first<<","<<vec[ind[i]].second<<")";
//	cout<<endl;
	int j=vec.size();
	for(int i=vec.size()-1;i>=0;--i){
		while(j==vec.size()||(j>=0&&vec[ind[j]].first>vec[i].second)){
			j--;
		}
		j++;
		if(j==vec.size())continue;
		int w=vec[ind[j]].first-vec[i].second-1;
		E.add(i+1,ind[j]+1,w);aE.add(ind[j]+1,i+1,w);//图上建点+1 
	}
	
//	for(int j=0;j<vec.size();++j){
	//	cout<<ind[j]<<" ";
//	}
//	cout<<endl;
	
	//还需要预处理:左端点>=L的情况下R最小的区间(nxt指针)
	j=vec.size();
	int lre_id=-1;
	for(int i=n;i>=1;--i){
	//	cout<<"i="<<i<<endl;
		while(j==vec.size()||(j>=0&&vec[ind[j]].first>=i)){
		//	cout<<"j="<<j<<endl;
			if(lre_id==-1||vec[ind[j]].second<vec[lre_id].second){
				if(j!=vec.size())lre_id=ind[j];
			}
			j--;
		}
		j++;
		nxt[i]=lre_id;
	//	cout<<"i="<<i<<" nxt="<<nxt[i]<<endl;
	} 
	
//	aE.show(vec.size());
	
	for(int i=vec.size()-1;i>=0;--i){
		if(!f[0][ind[i]+1]){
		//	cout<<"start from "<<ind[i]+1<<endl;
			depth[ind[i]+1]=0;
			dfs(ind[i]+1,&aE);
		}
	}
	
	while(q--){
		int L=read()^res,R=read()^res; 
	//	cout<<"real ask ("<<L<<","<<R<<")"<<endl;
		res=0;
		if(nxt[L]==-1){
			res=R-L+1;
		}else{
			int id=nxt[L],tp=id;
			if(vec[id].second>R){
				res=R-L+1;
			}else{
				id++;tp++;
			//	cout<<"id="<<id<<endl;
				res+=vec[id-1].first-L;//左边空出来的区间
				for(int i=20;i>=0;--i){
					if(f[i][tp]&&vec[f[i][tp]-1].second<=R){
						tp=f[i][tp];
					}
				} 
			//	cout<<"tp="<<tp<<endl;
				res+=depth[tp]-depth[id];
				res+=R-vec[tp-1].second;		
			}
		}
		printf("%d\n",res);
	}
	return 0;
}