#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
vector<pair<int,int>> seg(4*MAXN);
vector<int> wow(4*MAXN);
vector<int> haha(MAXN);
vector<int> pos(MAXN);
int N;
void build(int l, int r, int x) {
if(l == r) {
seg[x] = {haha[l],l};
return;
}
int mid = (l+r)/2;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
seg[x] = min(seg[x*2],seg[x*2+1]);
}
void upd(int l, int r, int ql, int qr, int x, int c) {
if(r < ql || l > qr) {
return;
}
if(l >= ql && r <= qr) {
seg[x] = {seg[x].first+c,seg[x].second};
wow[x]+=c;
return;
}
int mid = (l+r)/2;
upd(l,mid,ql,qr,x*2,c);
upd(mid+1,r,ql,qr,x*2+1,c);
seg[x] = min(seg[x*2],seg[x*2+1]);
seg[x] = {seg[x].first+wow[x],seg[x].second};
}
void init(int k, std::vector<int> r) {
N = r.size();
int n = N;
for(int i = 0; i < n; i++) {
haha[i] = r[i];
}
build(0,N-1,1);
set<int> idk;
queue<int> banana;
int br = 0;
for(int i = 0; i < n; i++) {
if(r[i] == 0) {
idk.insert(i-n);
idk.insert(i);
idk.insert(i+n);
banana.push(i);
}
}
while(!banana.empty()) {
int p = banana.front();
banana.pop();
if(idk.find(p) == idk.end()) {
continue;
}
if(*(--idk.upper_bound(p-1)) > p-k) {
continue;
}
pos[p] = br;
br++;
int x = *(idk.lower_bound(p));
if(x >= n) {
x-=n;
}
banana.push(x);
if(p >= k-1) {
upd(0,n-1,p-k+1,p-1,1,-1);
}
else {
upd(0,n-1,0,p-1,1,-1);
upd(0,n-1,n-(k-p-1),n-1,1,-1);
}
while(seg[1].first == 0) {
int q = seg[1].second;
idk.insert(q);
idk.insert(q-n);
idk.insert(q+n);
upd(0,n-1,q,q,1,1e9);
banana.push(q);
}
idk.erase(p);
idk.erase(p-n);
idk.erase(p+n);
}
return;
}
int compare_plants(int x, int y) {
if(pos[x] < pos[y]) {
return 1;
}
else {
return -1;
}
}
