#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);
pair<int,int> lift[MAXN][19][2];
int N,K;
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};
}
vector<int> dude(vector<int> yo, int k) {
int n = N;
set<pair<int,int>> idk;
for(int i = n-k+1; i < n; i++) {
idk.insert({yo[i],i});
}
int y = n-k+1;
vector<int> ans(n);
for(int i = 0; i < n; i++) {
int a = yo[i];
auto d = idk.lower_bound({a,-1});
if(d == idk.end()) {
ans[i] = -1;
}
else {
ans[i] = (*d).second;
}
idk.insert({a,i});
idk.erase({yo[y],y});
y++;
if(y == n) {
y = 0;
}
}
return ans;
}
void init(int k, std::vector<int> r) {
N = r.size();
K = k;
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);
upd(0,n-1,i,i,1,1e9);
}
}
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+1));
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);
}
vector<int> bro(n);
for(int i = 0; i < n; i++) {
bro[i] = pos[i];
}
vector<int> wut = dude(bro,k);
for(int i = 0; i < n; i++) {
int x = i-wut[i];
if(x < 0) {
x+=n;
}
lift[i][0][0] = {wut[i],x};
}
reverse(bro.begin(),bro.end());
wut = dude(bro,k);
reverse(wut.begin(),wut.end());
for(int i = 0; i < n; i++) {
int y = wut[i];
if(y != -1) {
y = n-y-1;
}
int x = y-i;
if(x < 0) {
x+=n;
}
lift[i][0][1] = {y,x};
}
for(int i = 1; i < 19; i++) {
for(int j = 0; j < n; j++) {
if(lift[j][i-1][0].first == -1) {
lift[j][i][0] = {-1,-1};
}
else {
lift[j][i][0] = {lift[lift[j][i-1][0].first][i-1][0].first,lift[lift[j][i-1][0].first][i-1][0].second+lift[j][i-1][0].second};
}
if(lift[j][i-1][1].first == -1) {
lift[j][i][1] = {-1,-1};
}
else {
lift[j][i][1] = {lift[lift[j][i-1][1].first][i-1][1].first,lift[lift[j][i-1][1].first][i-1][1].second+lift[j][i-1][1].second};
}
}
}
return;
}
bool yeah(int a, int d, int t, int y) {
int k = K;
for(int i = 18; i >= 0; i--) {
if(lift[a][i][t].first != -1 && lift[a][i][t].second <= d) {
d-=lift[a][i][t].second;
a = lift[a][i][t].first;
}
}
if(d >= k) {
return false;
}
if(pos[a] > pos[y]) {
return false;
}
return true;
}
int compare_plants(int x, int y) {
int ans;
int n = N;
if(pos[x] < pos[y]) {
ans = 1;
}
else {
swap(x,y);
ans = -1;
}
int d = x-y;
if(d < 0) {
d+=n;
}
if(yeah(x,d,0,y)) {
return ans;
}
d = y-x;
if(d < 0) {
d+=n;
}
if(yeah(x,n,1,y)) {
return ans;
}
return 0;
}
