1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 40000+100 14 #define maxm 200+50 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=n;i++) 19 #define for1(i,n) for(int i=1;i<=n;i++) 20 #define for2(i,x,y) for(int i=x;i<=y;i++)   21 using namespace std; 22 inline int read() 23 { 24     int x=0,f=1;char ch=getchar(); 25     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 26     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 27     return x*f; 28 } 29 int n,m,ans=0,block,a[maxn],c[maxn],d[maxn],pos[maxn],sum[maxn],f[maxm][maxn],g[maxm][maxm]; 30 struct rec{int x,id;}b[maxn]; 31 inline bool cmp(rec a,rec b) 32 { 33     return a.x<b.x; 34 } 35 void ask(int x,int y) 36 { 37     x=(x+ans-1)%n+1;y=(y+ans-1)%n+1; 38     if(x>y)swap(x,y); 39     int bx=pos[x],by=pos[y],cnt=0,tmp=0,xx=0; 40     if(by-bx<=1) 41     { 42         for2(i,x,y)d[++cnt]=a[i]; 43         sort(d+1,d+cnt+1); 44         for1(i,cnt) 45          { 46           tmp++; 47           if(i==cnt||d[i]!=d[i+1]) 48            { 49             if(tmp>xx||(tmp==xx&&d[i]<ans))xx=tmp,ans=d[i]; 50             tmp=0; 51            } 52          } 53     } 54     else 55     { 56         for2(i,x,bx*block)d[++cnt]=a[i]; 57         for2(i,(by-1)*block+1,y)d[++cnt]=a[i]; 58         sort(d+1,d+cnt+1); 59         ans=g[bx+1][by-1];xx=f[by-1][ans]-f[bx][ans]; 60         for1(i,cnt) 61          { 62              tmp++; 63              if(i==cnt||d[i]!=d[i+1]) 64              { 65                  tmp+=f[by-1][d[i]]-f[bx][d[i]]; 66                  if(tmp>xx||(tmp==xx&&d[i]<ans))xx=tmp,ans=d[i]; 67                  tmp=0; 68              } 69          } 70     } 71     ans=c[ans]; 72     printf("%d\n",ans); 73 } 74 int main() 75 { 76     freopen("input.txt","r",stdin); 77     freopen("output.txt","w",stdout); 78     n=read();m=read(); 79     for1(i,n)b[i].x=read(),b[i].id=i; 80     sort(b+1,b+n+1,cmp); 81     int tot=0; 82     for1(i,n) 83     { 84         if(i==1||b[i].x!=b[i-1].x)tot++; 85         a[b[i].id]=tot; 86         c[tot]=b[i].x; 87     } 88     block=floor(sqrt(n)); 89     for1(i,n) 90      { 91          pos[i]=(i-1)/block+1; 92          sum[a[i]]++; 93          if(i==n||i==pos[i]*block)for1(j,tot)f[pos[i]][j]=sum[j]; 94      } 95     for1(i,pos[n]) 96      for2(j,i,pos[n]) 97       { 98           ans=g[i][j-1]; 99           for2(k,(j-1)*block+1,min(j*block,n))100           if(f[j][a[k]]-f[i-1][a[k]]>f[j][ans]-f[i-1][ans]||101             (f[j][a[k]]-f[i-1][a[k]]==f[j][ans]-f[i-1][ans]&&a[k]<ans))ans=a[k];102         g[i][j]=ans;   103       }104     ans=0;  105     while(m--)ask(read(),read());106     return 0;107 }