#include "plants.h"
#include "bits/stdc++.h"
#define MAXN 100009
#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,s[MAXN<<2],arr[MAXN];
void build(int nd=1,int x=0,int y=n-1){
for(int i=x;i<=y;i++)s[i]=arr[i];
}
void inc(int l,int r,int val,int nd=1,int x=0,int y=n-1){
for(int i=l;i<=r;i++)s[i]+=val;
}
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(){
for(int i=0;i<n;i++)
if(!s[i])
return i;
return -1;
}
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 flex(int x,int y){
while(x!=y){
if(!s[x])tmp.pb(x);
x=(x+1)%n;
}if(!s[y])tmp.pb(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--){
//print();
int res=get();
h[res]=i;
//debug(res);
int pre=(res-K+1+n)%n;
int nex=(res+K-1)%n;
//cout<<pre<<" "<<nex<<endl;
upd(res,res,INF);
upd(pre,res,-1);
upd(res,nex,-1);
//print();
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;
}
