#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,k,R[200009],cnt,f[200009],seg[800009],seg2[800009],segmn[800009],za,l,r,z,zz;
set <int> s;
set <int>::iterator it,tt;
set <pair <int, int> > st;
set <pair <int, int> >::iterator IT;
void pushdown(int q, int w, int rr){
if(q!=w){
seg2[rr*2]+=seg2[rr];
seg2[rr*2+1]+=seg2[rr];
}
segmn[rr]+=seg2[rr];
seg2[rr]=0;
}
void upd(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
seg2[rr]+=z;
pushdown(q,w,rr);
return;
}
upd(q,(q+w)/2,rr*2);
upd((q+w)/2+1,w,rr*2+1);
if(segmn[rr*2]<segmn[rr*2+1]){
seg[rr]=seg[rr*2];segmn[rr]=segmn[rr*2];
}
if(segmn[rr*2]>segmn[rr*2+1]){
seg[rr]=seg[rr*2+1];segmn[rr]=segmn[rr*2+1];
}
if(segmn[rr*2]==segmn[rr*2+1]){
segmn[rr]=segmn[rr*2+1];
seg[rr]=min(seg[rr*2],seg[rr*2+1]);
}
}
void UPD(int q, int w, int rr){
l=q+1;r=w+1;z=rr;
upd(1,za,1);
}
void read(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
if(z>segmn[rr]){
z=segmn[rr];zz=seg[rr];
}else{
if(z==segmn[rr]){
if(zz>seg[rr]) zz=seg[rr];
}
}
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
void READ(int q, int w){
q++;w++;
while(q<=w){
l=q;r=w;z=a+3;zz=a+3;
read(1,za,1);
if(z!=0||zz>w) break;
zz--;
it=s.lower_bound(zz);
if(it==s.end()) it=s.begin();
if(it!=s.begin()){
tt=it;tt--;
}else{
tt=s.end();tt--;
}
st.erase(st.lower_bound(make_pair(((*it)+a-(*tt))%a,(*it))));
st.insert(make_pair(((*it)+a-zz)%a,(*it)));
st.insert(make_pair((zz+a-(*tt))%a,zz));
s.insert(zz);
zz++;
q=zz+1;
}
}
void init(int Kk, vector<int> Rr) {
a=Rr.size();k=Kk-1;
for(i=0; i<a; i++){
R[i]=Rr[i];
}
za=1;
while(za<a) za*=2;
for(i=0; i<a; i++){
seg[za+i]=i+1;segmn[za+i]=R[i];
if(R[i]==0){
s.insert(i);
}
}
for(i=za-1; i>=1; i--){
if(segmn[i*2]<segmn[i*2+1]){
seg[i]=seg[i*2];segmn[i]=segmn[i*2];
}
if(segmn[i*2]>segmn[i*2+1]){
seg[i]=seg[i*2+1];segmn[i]=segmn[i*2+1];
}
if(segmn[i*2]==segmn[i*2+1]){
segmn[i]=segmn[i*2+1];
seg[i]=min(seg[i*2],seg[i*2+1]);
}
}
for(it=s.begin(); it!=s.end(); it++){
tt=it;tt++;
/*if(tt==s.end()){
tt=s.begin();
st.insert(make_pair((*tt)+a-(*it),(*tt)));
}else{
st.insert(make_pair((*tt)-(*it),(*tt)));
}*/
if(tt==s.end()) tt=s.begin();
st.insert(make_pair(((*tt)+a-(*it))%a,(*tt)));
}
cnt=a;
/*cout<<cnt<<" JJF";
exit(0);*/
//cout<<s.size()<<" "<<st.size()<<endl;
while(cnt>0){
IT=st.end();IT--;
i=(*IT).second;
f[i]=cnt;cnt--;
if(cnt==0) break;
if(i-k>=0){
UPD(i-k,i-1,-1);
READ(i-k,i-1);
}else{
UPD(0,i-1,-1);
UPD(a-(k-i),a-1,-1);
READ(0,i-1);
READ(a-(k-i),a-1);
}
/*cout<<i<<" kala1"<<endl;
cout<<s.size()<<" "<<st.size()<<endl;
exit(0);*/
s.erase(s.lower_bound(i));
it=s.lower_bound(i);
if(it==s.end()) it=s.begin();
if(it!=s.begin()){
tt=it;tt--;
}else{
tt=s.end();tt--;
}
st.erase(st.lower_bound(make_pair(((*it)+a-i)%a,(*it))));
st.erase(st.lower_bound(make_pair((i+a-(*tt))%a,i)));
st.insert(make_pair(((*it)+a-(*tt))%a,(*it)));
/*cout<<i<<" kala2";
exit(0);*/
l=i+1;r=i+1;z=a+3;
upd(1,za,1);
/*cout<<i<<" kala3";
exit(0);*/
}
return;
}
int compare_plants(int x, int y) {
if(f[x]>f[y]){
return 1;
}else{
return -1;
}
return 0;
}
/*int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int TES=0,TE=0;
cin>>a>>k>>TES;
vector <int> Rr;
Rr.resize(a);
for(i=0; i<a; i++){
cin>>R[i];
//Rr.push_back(c);
}
for(i=0; i<a; i++){
for(j=i+1; j<i+k; j++){
if(R[j%a]>R[i]) Rr[i]++;
}
}
init(k,Rr);
for(i=0; i<a; i++){
cout<<f[i]<<" ";
}
cout<<endl;
return 0;
for(TE=1; TE<=TES; TE++){
cin>>c>>d;
cout<<compare_plants(c,d)<<endl;
}
return 0;
}*/
