#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int NN=2e5+100;
int a[NN];
int seg[4*NN];
int lazy[4*NN];
int nn;
vector<int> vec;
void fix(int p,int s,int e)
{
seg[p]+=lazy[p];
if(s!=e){
lazy[p*2]+=lazy[p];
lazy[p*2+1]+=lazy[p];
}
lazy[p]=0;
}
void update(int p,int s,int e,int a,int b,int v)
{
fix(p,s,e);
if(a<=s&&e<=b){
lazy[p]+=v;
fix(p,s,e);
return;
}
if(a>e||b<s)return;
int mid=(s+e)/2;
update(p*2,s,mid,a,b,v);
update(p*2+1,mid+1,e,a,b,v);
seg[p]=min(seg[p*2],seg[p*2+1]);
}
int get(int p,int s,int e)
{
fix(p,s,e);
if(s==e){
return s;
}
int mid=(s+e)/2;
fix(p*2,s,mid);
if(seg[p*2]==0){
return get(p*2,s,mid);
}
else{
return get(p*2+1,mid+1,e);
}
}
void get2(int p,int s,int e,int a,int b)
{
fix(p,s,e);
if(seg[p]!=0||s>b||e<a)return ;
if(s==e){
vec.push_back(s);
return;
}
int mid=(s+e)/2;
get2(p*2,s,mid,a,b);
get2(p*2+1,mid+1,e,a,b);
}
void upd(int a,int b,int v)
{
if(a<=b){
update(1,0,nn-1,a,b,v);
if(v<0)get2(1,0,nn-1,a,b);
// cout<<a<<" "<<b<<" "<<v<<endl;
}
else{
update(1,0,nn-1,a,nn-1,v);
if(v<0)get2(1,0,nn-1,a,nn-1);
update(1,0,nn-1,0,b,v);
if(v<0)get2(1,0,nn-1,0,b);
// cout<<a<<" "<<nn-1<<" "<<v<<endl;
// cout<<0<<" "<<b<<" "<<v<<endl;
}
}
void build(int p,int s,int e)
{
fix(p,s,e);
if(s==e){
// cout<<"s "<<s<<" "<<seg[p]<<endl;
return;
}
int mid=(s+e)/2;
build(p*2,s,mid);
build(p*2+1,mid+1,e);
}
void init(int k,vector<int> r){
nn=r.size();
int cnt=nn;
for(int i=0;i<nn;i++){
upd(i,i,r[i]);
if(r[i]==0){
int ll=(i+1)%nn;
int rr=(i+k-1+nn)%nn;
upd(ll,rr,+1);
// cout<<ll<<" "<<rr<<" "<<+1<<endl;
}
}
while(seg[1]==0){
vec.clear();
// build(1,0,nn-1);
int i=get(1,0,nn-1);
a[i]=cnt--;
upd(i,i,1e8);
int ll=(i+1)%nn;
int rr=(i+k-1+nn)%nn;
upd(ll,rr,-1);
// cout<<ll<<" "<<rr<<" "<<-1<<endl;
rr=(i-1+nn)%nn;
ll=(i-k+1+nn)%nn;
upd(ll,rr,-1);
for(auto x:vec){
upd(x+1,(x+k-1+nn)%nn,1);
}
// cout<<ll<<" "<<rr<<" "<<-1<<endl;
}
// cout<<seg[1]<<endl;
//for(int i=0;i<nn;i++)cout<<a[i]<<" ";cout<<endl;
}
int compare_plants(int x, int y){
if(a[x]<a[y])return -1;
else return 1;
}
/*
54321
00012
*/
