#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef int ll;
namespace{
const ll mxN=2e5+5; // warning remember to build
const ll inf=1e9;
struct segtree{
vector<array<ll, 3>> tree;
ll siz;
void init(ll sz){
siz=sz+1;
tree=vector<array<ll, 3>> (siz, {0, 0, 0});
}
void update(ll qlow, ll qhigh, ll id, ll val){
for(ll i=qlow;i<=qhigh;i++){
tree[i][id]+=val;
}
}
array<ll, 3> getmin(ll qlow, ll qhigh){
array<ll, 3> re={inf, inf, inf};
for(ll i=qlow;i<=qhigh;i++){
re=min(re, tree[i]);
}
return re;
}
};
ll n, k;
vll adj[mxN];
// ll ans[mxN][mxN];
bool done[mxN];
ll val[mxN];
bool visited[mxN];
segtree seg;
void dfs(ll cur){
if(visited[cur]) return;
visited[cur]=1;
for(auto &it:adj[cur]){
dfs(it);
}
}
}
void init(int K, vector<int> a) {
memset(done, 0, sizeof(done));
// memset(ans, 0, sizeof(ans));
n=a.size();
k=K;
if(2*k>n){
seg.init(n);
for(ll i=0;i<n;i++){
seg.tree[i]={a[i], 0, i};
}
// seg.build(1, 0, seg.treelen-1);
auto add=[&](ll idx){
ll lef=(idx+1)%n;
ll rig=(idx+k-1)%n;
if(lef>rig){
seg.update(lef, n-1, 1, 1);
seg.update(0, rig, 1, 1);
}
else{
seg.update(lef, rig, 1, 1);
}
};
for(ll i=0;i<n;i++){
if(a[i]==0){
add(i);
}
}
for(ll i=n-1;i>=0;i--){
// vll tep;
// for(ll j=0;j<n;j++){
// if(!done[j] && a[j]==0){
// tep.pb(j);
// }
// }
ll dumb=0;
array<ll, 3> tep=seg.getmin(0, n-1);
dumb=tep[2];
assert(tep[0]==0);
assert(tep[1]==0);
// if((ll) tep.size()==1){
// dumb=tep[0];
// }
// else{
// for(ll j=0;j<(ll) tep.size();j++){
// ll pre=(j-1+(ll) tep.size())%((ll) tep.size());
// if(((tep[j]-tep[pre]+n)%n)>=k){
// dumb=tep[j];
// break;
// }
// }
// }
val[dumb]=i;
seg.update(dumb, dumb, 0, inf);
ll lef=(dumb+1)%n;
ll rig=(dumb+k-1)%n;
if(lef>rig){
seg.update(lef, n-1, 1, -1);
seg.update(0, rig, 1, -1);
}
else{
seg.update(lef, rig, 1, -1);
}
lef=(dumb-k+1+n)%n;
rig=(dumb-1+n)%n;
if(lef>rig){
seg.update(lef, n-1, 0, -1);
seg.update(0, rig, 0, -1);
ll pre=lef;
while(true){
ll l=pre, r=n-1;
ll good=-1;
while(l<=r){
ll mid=(l+r)/2;
array<ll, 3> pooh=seg.getmin(mid, n-1);
if(pooh[0]==0){
good=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
if(good==-1) break;
add(good);
pre=good+1;
}
pre=0;
while(true){
ll l=pre, r=rig;
ll good=-1;
while(l<=r){
ll mid=(l+r)/2;
array<ll, 3> pooh=seg.getmin(mid, n-1);
if(pooh[0]==0){
good=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
if(good==-1) break;
add(good);
pre=good+1;
}
}
else{
seg.update(lef, rig, 0, -1);
ll pre=lef;
while(true){
ll l=pre, r=rig;
ll good=-1;
while(l<=r){
ll mid=(l+r)/2;
array<ll, 3> pooh=seg.getmin(mid, n-1);
if(pooh[0]==0){
good=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
if(good==-1) break;
add(good);
pre=good+1;
}
}
}
return;
// for(ll i=0;i<n;i++){
// cout<<val[i]<<' ';
// }
// cout<<'\n';
}
// auto check=[&](ll tar){
// if(a[tar]>0) return false;
// if(done[tar]) return false;
// ll cur=tar;
// for(ll i=0;i<k-1;i++){
// cur--;
// if(cur<0) cur+=n;
// if(done[cur]) continue;
// if(a[cur]==0) return false;
// }
// return true;
// };
// for(ll rep=0;rep<n;rep++){
// ll cur=-1;
// for(ll tar=0;tar<n;tar++){
// if(check(tar)){
// cur=tar;
// break;
// }
// }
// done[cur]=1;
// for(ll i=1;i<k;i++){
// ll cur2=(cur+i)%n;
// if(done[cur2]) continue;
// adj[cur].pb(cur2);
// }
// for(ll i=1;i<k;i++){
// ll cur2=(cur-i+n)%n;
// if(done[cur2]) continue;
// a[cur2]--;
// adj[cur].pb(cur2);
// }
// }
// for(ll i=0;i<n;i++){
// memset(visited, 0, sizeof(visited));
// dfs(i);
// for(ll j=0;j<n;j++){
// if(visited[j]){
// ans[i][j]=1;
// ans[j][i]=-1;
// }
// }
// }
}
int compare_plants(int x, int y) {
// if(2*k>n){
if(val[x]>val[y]) return 1;
return -1;
// }
// return (int) ans[x][y];
}
