#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,cnt,q,x,y,k,a[N],f[N],dp[1001][1001],c[N],bel[N],L[N],R[N],lz[N],blo;
vector<int>C[N];
unordered_map<int,int>d;
inline int count(int l,int r,int k){
    return upper_bound(C[k].begin(),C[k].end(),y)-lower_bound(C[k].begin(),C[k].end(),x);
}
inline void build(int n){
    blo=sqrt(n);
    cnt=(n+blo-1)/blo;
    for(int i=1;i<=cnt;i++){
        L[i]=(i-1)*blo+1;
        R[i]=i*blo;
    }
    R[cnt]=n;
    for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
}
inline int qmax(int x,int y){
    int ans=0,b=1e18,p;
    if(bel[x]==bel[y]){
        memset(c,0,sizeof c);
        for(int i=x;i<=y;i++){
            c[a[i]]++;
            if(ans<c[a[i]]) ans=c[a[i]],b=a[i];
            else if(ans==c[a[i]]) b=min(b,a[i]);
        }
        return b;
    }
    for(int i=x;i<=R[bel[x]];i++){
        p=count(x,y,a[i]);
        if(p>ans) ans=p,b=a[i];
        else if(p==ans) b=min(b,a[i]);
    }
    for(int i=L[bel[y]];i<=y;i++){
        p=count(x,y,a[i]);
        if(p>ans) ans=p,b=a[i];
        else if(p==ans) b=min(b,a[i]);
    }
    p=count(x,y,dp[bel[x]+1][bel[y]-1]);
    if(p>ans) ans=p,b=dp[bel[x]+1][bel[y]-1];
    else if(p==ans) b=min(b,dp[bel[x]+1][bel[y]-1]);
    return b;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n>>q&&n&&q){
		for(int i=1;i<=n;i++) cin>>a[i],f[i]=a[i];
		build(n);
		sort(f+1,f+1+n);
		for(int i=1;i<=n;i++) d[f[i]]=i;
		for(int i=1;i<=n;i++) a[i]=d[a[i]],C[a[i]].clear();
		for(int i=1;i<=n;i++) C[a[i]].push_back(i);
		for(int i=1;i<=cnt;i++){
			memset(c,0,sizeof c);
			int b=1e18,ans=0;
			for(int j=i;j<=cnt;j++){
				for(int k=L[j];k<=R[j];k++){
					c[a[k]]++;
					if(c[a[k]]>ans) ans=c[a[k]],b=a[k];
					else if(c[a[k]]==ans) b=min(b,a[k]);
				}
				dp[i][j]=b;
			}
		}
		while(q--){
			cin>>x>>y;
			cout<<count(x,y,qmax(x,y))<<'\n';
		}
	}
}