1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<utility>
#include<cstring>
#include<cctype>
using namespace std;
inline int read(){
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
typedef pair<int,int> pii;
namespace star
{
const int maxn=40010,block=1500,maxm=50;
int n,m,a[maxn],cnt,cn=1;
int belong[maxn],beg[maxm],end[maxm],num[maxm][maxm][maxn],maxx[maxm][maxm];
int ed[maxn],time=0;
int color[maxn],id[maxn];
int con[maxn];
pii p[maxn];
inline void solve(){
int l=0,r=0,ans=0;
while(m--){
time++;
l=(read()+ans-1)%n+1,r=(read()+ans-1)%n+1;
if(l>r)swap(l,r);
ans=0;
int mx=0,mxid=0;
if(belong[l]==belong[r]){
for(int i=l;i<=r;i++)
{
if(ed[id[i]]!=time)con[id[i]]=0,ed[id[i]]=time;
con[id[i]]++;
if(con[id[i]]>mx or (con[id[i]]==mx and id[i]<mxid))mxid=id[i],mx=con[mxid];
}
ans=color[mxid];
printf("%d\n",ans);
}else{
int L=belong[l]+1,R=belong[r]-1;
mxid=maxx[L][R];mx=num[L][R][mxid];
for(int i=l;i<beg[L];i++)
{
if(ed[id[i]]!=time)con[id[i]]=0,ed[id[i]]=time;
con[id[i]]++;
if(con[id[i]]+num[L][R][id[i]]>mx or (con[id[i]]+num[L][R][id[i]]==mx and id[i]<mxid))mxid=id[i],mx=con[mxid]+num[L][R][id[i]];
}
for(int i=end[R]+1;i<=r;i++)
{
if(ed[id[i]]!=time)con[id[i]]=0,ed[id[i]]=time;
con[id[i]]++;
if(con[id[i]]+num[L][R][id[i]]>mx or (con[id[i]]+num[L][R][id[i]]==mx and id[i]<mxid))mxid=id[i],mx=con[mxid]+num[L][R][id[i]];
}
ans=color[mxid];
printf("%d\n",ans);
}
}
}
inline void makeblock(){
beg[1]=1;
cn=1;
for(int i=1;i<=n;i++){
if(!(i%block)){
end[cn]=i-1;
cn++;
beg[cn]=i;
}
belong[i]=cn;
}
if(n%block)cn++;
end[cn]=n;
for (int i = 1; i <= cn; i++)
for (int j = i; j <= cn; j++)
{
int makk = 0;
for (int k = beg[i]; k <= end[j]; k++)
num[i][j][id[k]]++;
for (int k = 1; k <= cnt; k++){
if(makk<num[i][j][k]) {
makk=num[i][j][k];
maxx[i][j]=k;
}
}
}
}
inline void cried()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
p[i]=make_pair(read(),i);
sort(p+1,p+n+1);
for(int i=1;i<=n;i++){
if(p[i].first!=p[i-1].first or i==1)cnt++;
color[cnt]=p[i].first;
id[p[i].second]=cnt;
}
makeblock();
solve();
}
}
int main()
{
star::cried();
return 0;
}
|
