#include "plants.h"
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int h[MAXN],n,k,lazy[MAXN<<2],arr[MAXN];
PII s[MAXN<<2];
void build(int nd=1,int x=0,int y=n-1){
if(x==y){
s[nd]=mp(arr[x],x);
return;
}
int mid=(x+y)>>1;
build(nd<<1,x,mid);
build(nd<<1|1,mid+1,y);
s[nd]=min(s[nd<<1],s[nd<<1|1]);
}
void shift(int nd){
int &ret=lazy[nd];if(!ret)return;
lazy[nd<<1]+=ret;s[nd<<1].ff+=ret;
lazy[nd<<1|1]+=ret;s[nd<<1|1].ff+=ret;
ret=0;
}
void inc(int l,int r,int val,int nd=1,int x=0,int y=n-1){
if(l>y or x>r)
return;
if(l<=x and y<=r){
s[nd].ff+=val;
lazy[nd]+=val;
return;
}
shift(nd);
int mid=(x+y)>>1;
inc(l,r,val,nd<<1,x,mid);
inc(l,r,val,nd<<1|1,mid+1,y);
s[nd]=min(s[nd<<1],s[nd<<1|1]);
}
void upd(int x,int y,int val){
if(x<=y)inc(x,y,val);
else inc(x,n-1,val),inc(0,y,val);
}
int get(){assert(s[1].ff==0);return s[1].ss;}
int vis[MAXN];
vector<int>tmp;
void zero(int i){
if(vis[i])return;vis[i]=1;
upd(i+1,(i+k-1)%n,1);
}
void tap(int l,int r,int nd=1,int x=0,int y=n-1){
if(l>y or x>r or s[nd].ff>0)return;
if(x==y){
tmp.pb(x);
return;
}shift(nd);
int mid=(x+y)>>1;
tap(l,r,nd<<1,x,mid);
tap(l,r,nd<<1|1,mid+1,y);
s[nd]=min(s[nd<<1],s[nd<<1|1]);
}
void flex(int x,int y){
if(x<=y)tap(x,y);
else tap(x,n-1),tap(0,y);
}
void print(){
for(int i=0;i<n;i++)printf("%d ",s[i]);puts("");
}
void init(int K, vector<int> r) {
n=int(r.size());k=K;
for(int i=0;i<n;i++)arr[i]=r[i];
build();
for(int i=0;i<n;i++)
if(!arr[i])
zero(i);
for(int i=n-1;i>=0;i--){
int res=get();h[res]=i;
//debug(res);
int pre=(res-K+1+n)%n;
int nex=(res+K-1)%n;
upd(res,res,INF);
upd(pre,res,-1);upd(res,nex,-1);
flex(pre,res);flex(res,nex);
tr(it,tmp)zero(*it);tmp.clear();
}
}
int compare_plants(int x, int y) {
int ans=0;
ans+=(h[x]>h[y]);
ans-=(h[x]<h[y]);
return ans;
}
