YLST3的算法， $O(x\sqrt n)$，样例过了，WA 0pts。

#include <bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#pragma GCC target("sse,sse2,sse3,mmx")
#define C puts("zqw")
#define D cout << aans << ":"
using namespace std;
int qr(){
    int x=0,f=0;
    char c=getchar();
    while(c>'9'||c<'0') f|=(c=='-'),c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
const int maxn=40005,maxsn=205;
int n,m,s,flag[maxn],a[maxn],idx[maxn],L[maxsn],R[maxsn],xb[maxn],ton[maxn],f[maxsn][maxsn],ff[maxsn][maxsn],l,r,ans,bls,top=0,aans;
vector<int> pos[maxn];
int main() {
//	freopen("P4168_1.in","r",stdin);
    n=qr(),m=qr();
    s=sqrt(n);
    bls=(n+s-1)/s;
    for(int i=1;i<=n;++i) flag[i]=a[i]=qr();
    sort(flag+1,flag+n+1);
    for(int i=1;i<=n;++i){
    	if(flag[i]!=flag[i-1]){
    		flag[++top]=flag[i];
		}
	}
    for(int i=1;i<=n;++i) {
        a[i]=lower_bound(flag+1,flag+top+1,a[i])-flag;
        pos[a[i]].push_back(i);
        xb[i]=pos[a[i]].size()-1;
    }
    for(int i=1;i<=bls;++i){
    	L[i]=R[i-1]+1,R[i]=min(n,i*s);
    	for(int j=L[i];j<=R[i];++j) idx[j]=i;
	}
    for(int i=2;i<bls;++i){
    	for(int j=i;j<bls;++j){
    		f[i][j]=f[i][j-1];
    		for(int k=L[j];k<=R[j];++k){
    			++ton[a[k]];
    			if(ton[a[k]]>f[i][j]) f[i][j]=ton[a[k]],ff[i][j]=a[k];
    			if(ff[i][j]==0||(f[i][j]==ton[a[k]]&&ff[i][j]>a[k])) ff[i][j]=a[k];
    			
			}
		}
		memset(ton,0,sizeof(ton));
	}
    while(m--){
        l=qr(),r=qr();
        l=(flag[aans]+l-1)%n+1,r=(flag[aans]+r-1)%n+1;
        if(l>r) l=l+r-(r=l);
        if(idx[l]==idx[r]){
        	ans=0,aans=INT_MAX;
            for(int i=l;i<=r;++i){
            	++ton[a[i]];
				ans=max(ans,ton[a[i]]);
				if(ton[a[i]]>ans){
					ans=a[i];
					aans=a[i];
				}
				if(ton[a[i]]==ans&&a[i]<aans){
					aans=a[i];
				}
			}
            for(int i=l;i<=r;++i)ton[a[i]]=0;
        }else{
            ans=f[idx[l]+1][idx[r]-1];
            aans=ff[idx[l]+1][idx[r]-1];
            for(int i=l;i<=R[idx[l]];++i){
                while(pos[a[i]].size()>ans+xb[i]&&pos[a[i]][ans+xb[i]]<=r){
                    ++ans;
                    aans=a[i];
                }
                if(pos[a[i]].size()==ans+xb[i]&&pos[a[i]][ans+xb[i]]<=r&&a[i]<aans){
                	aans=a[i];
				}
            }
            for(int i=L[idx[r]];i<=r;++i){
                while(xb[i]-ans>=0&&pos[a[i]][xb[i]-ans]>=l){
                    ++ans;
                    aans=a[i];
                }
                if(xb[i]-ans==-1&&pos[a[i]][xb[i]-ans+1]>=l&&a[i]<aans){
                	aans=a[i];
				}
            }
        }
        printf("%d\n",flag[aans]);
    }
    return 0;
}