#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+5,L=1501;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void write(int x){
    if(x<0)x=-x,putchar('-');
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int n,m,blen,btot,q;
static int a[N],p[N];
static int sr[L],ed[L];
static int zs[L][L];
vector<int> su[L];
unordered_map<int,int> hsh;
unordered_map<int,int> mp;
int b[N];
void lsh(){
	for(int i=1;i<=n;i++)b[i]=a[i];
	sort(b+1,b+1+n);m=0;
	for(int i=1;i<=n;i++)if(i==1||b[i]!=b[i-1])hsh[b[i]]=++m,mp[m]=b[i];
	for(int i=1;i<=n;i++)a[i]=hsh[a[i]];
}
static int geshu[N];
void build(){
	blen=sqrt((double)n/2.2);
	for(int i=1;i<=n;i++)p[i]=(i-1)/blen+1;
	for(int i=1;i<=n;i++)ed[p[i]]=i;btot=p[n];
	for(int i=n;i>=1;i--)sr[p[i]]=i;
	for(int i=1;i<=btot;i++){
		memset(geshu,0,sizeof geshu);
		int nowz=1,zmax=0,j=i;
		for(int k=sr[i];k<=n;k++){
			geshu[a[k]]++;
			if(geshu[a[k]]>zmax || (geshu[a[k]]==zmax && a[k]<nowz) ){zmax=geshu[a[k]];nowz=a[k];}
			if(k==ed[j])zs[i][j++]=nowz;
		}
	}
	memset(geshu,0,sizeof geshu);
	for(int j=0;j<=m;j++)su[0].push_back(0);
	for(int i=1;i<=btot;i++){
		su[i].push_back(0);
		for(int j=1;j<=m;j++)su[i].push_back(su[i-1][j]);
		for(int k=sr[i];k<=ed[i];k++)su[i][a[k]]++;
	}
}
inline int query(int l,int r){
	if(p[r]-p[l]<=0){
		int nowz=0;
		for(int i=l;i<=r;i++){
			geshu[a[i]]++;
			if(geshu[a[i]]>geshu[nowz] || (geshu[a[i]]==geshu[nowz] && a[i]<nowz) )nowz=a[i];
		}
		int ans=geshu[nowz];
		for(int i=l;i<=r;i++)geshu[a[i]]--;
		return ans;
	}
	int nowz=zs[p[l]+1][p[r]-1];
	for(int i=l;p[l]==p[i];i++){
		geshu[a[i]]++;
		if(geshu[a[i]]+su[p[r]-1][a[i]]-su[p[l]][a[i]]>geshu[nowz]+su[p[r]-1][nowz]-su[p[l]][nowz] || (geshu[a[i]]+su[p[r]-1][a[i]]-su[p[l]][a[i]]==geshu[nowz]+su[p[r]-1][nowz]-su[p[l]][nowz] && a[i]<nowz))nowz=a[i];
	}
	for(int i=r;p[r]==p[i];i--){
		geshu[a[i]]++;
		if(geshu[a[i]]+su[p[r]-1][a[i]]-su[p[l]][a[i]]>geshu[nowz]+su[p[r]-1][nowz]-su[p[l]][nowz] || (geshu[a[i]]+su[p[r]-1][a[i]]-su[p[l]][a[i]]==geshu[nowz]+su[p[r]-1][nowz]-su[p[l]][nowz] && a[i]<nowz))nowz=a[i];
	}
	int ans=geshu[nowz]+su[p[r]-1][nowz]-su[p[l]][nowz];
	int i;
	for(i=l;p[l]==p[i];i+=5){
		geshu[a[i]]--;
		geshu[a[i+1]]--;
		geshu[a[i+2]]--;
		geshu[a[i+3]]--;
		geshu[a[i+4]]--;
	}
	if(p[l]!=p[i-1])geshu[a[i-1]]++;
	if(p[l]!=p[i-2])geshu[a[i-2]]++;
	if(p[l]!=p[i-3])geshu[a[i-3]]++;
	if(p[l]!=p[i-4])geshu[a[i-4]]++;
	for(i=r;p[r]==p[i];i-=5){
		geshu[a[i]]--;
		geshu[a[i-1]]--;
		geshu[a[i-2]]--;
		geshu[a[i-3]]--;
		geshu[a[i-4]]--;
	}
	if(p[r]!=p[i+1])geshu[a[i+1]]++;
	if(p[r]!=p[i+2])geshu[a[i+2]]++;
	if(p[r]!=p[i+3])geshu[a[i+3]]++;
	if(p[r]!=p[i+4])geshu[a[i+4]]++;
	return ans;
}
signed main(){
	n=read(),q=read();
	for(int i=1;i<=n;i++)a[i]=read();
	lsh();build();int lst=0;
	while(q--){
		int l=read()^lst,r=read()^lst;
		write(lst=query(l,r));putchar('\n');
	}
    return 0;
}

https://www.luogu.com.cn/record/228802756