#include<bits/stdc++.h>
#include "plants.h"
using namespace std;
#define ll long long
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
const int MX=2e5+7;
const int MOD=1e9+7;
const int LG=20;
pair<int,int> seg[4*MX];
int lz[4*MX];
vector<int> vec;
int n;
int lef[LG][MX];
int rig[LG][MX];
void refresh(int pos, int l, int r){
if(lz[pos]==0)return;
seg[pos].first+=lz[pos];
if(l==r){
lz[pos]=0;return;
}
lz[2*pos]+=lz[pos];
lz[2*pos+1]+=lz[pos];
lz[pos]=0;
}
void build(int pos, int ini, int fim){
if(ini==fim){
seg[pos]={vec[ini],ini};
return;
}
int m=(ini+fim)/2;
int e=2*pos,d=2*pos+1;
build(e,ini,m);
build(d,m+1,fim);
seg[pos]=min(seg[e],seg[d]);
}
pair<int,int> query(int pos, int ini, int fim, int l, int r){
refresh(pos,ini,fim);
if(ini>r || fim<l)return make_pair(MOD,MOD);
if(l<=ini && fim <=r)return seg[pos];
int m=(ini+fim)/2;
return min(query(2*pos,ini,m,l,r),query(2*pos+1,m+1,fim,l,r));
}
pair<int,int> query(int ini, int fim){
if(ini<0)ini+=n;
if(fim<0)fim+=n;
if(fim>=n)fim-=n;
if(ini>=n)ini-=n;
if(ini<=fim){
return query(1,0,n-1,ini,fim);
}
else{
auto a=query(1,0,n-1,0,fim);
auto b=query(1,0,n-1,ini,n-1);
if(b.first<=a.first)return b;
else return a;
}
}
void update(int pos, int ini,int fim,int l, int r,int val){
refresh(pos,ini,fim);
if(ini>r || fim<l)return;
if(l<= ini && fim <=r){
lz[pos]+=val;
refresh(pos,ini,fim);
return;
}
int m=(ini+fim)/2;
int e=2*pos,d=2*pos+1;
update(e,ini,m,l,r,val);
update(d,m+1,fim,l,r,val);
seg[pos]=min(seg[e],seg[d]);
}
void update(int ini, int fim,int val){
if(ini<0)ini+=n;
if(fim<0)fim+=n;
if(fim>=n)fim-=n;
if(ini>=n)ini-=n;
if(ini<=fim){
update(1,0,n-1,ini,fim,val);
return;
}
update(1,0,n-1,0,fim,val);
update(1,0,n-1,ini,n-1,val);
}
bool pular(int a, int b){
if(a==b)return true;
int x=a;
if(a<b){
R(i,LG-1,0){
if(rig[i][x]<=b && rig[i][x]>=x)x=rig[i][x];
}
if(x==b)return true;
}
else{
R(i,LG-1,0){
if(rig[i][x]>=x && rig[i][x]<n)x=rig[i][x];
}
x=rig[0][x];
if(x<=b && pular(x,b))return true;
}
return false;
}
bool pulal(int a, int b){
if(a==b)return true;
int x=a;
if(a>b){
R(i,LG-1,0){
if(lef[i][x]>=b && lef[i][x]<=x)x=lef[i][x];
}
if(x==b)return true;
}
else{
R(i,LG-1,0){
if(lef[i][x]>=0 && lef[i][x]<=x)x=lef[i][x];
}
x=lef[0][x];
if(x>=b && pular(x,b))return true;
}
return false;
}
void init(int k, std::vector<int> A) {
vec=A;
n=sz(vec);
build(1,0,n-1);
queue<int> fila;
L(i,0,n-1){
if(vec[i]==0)fila.push(i);
}
vector<int> ord;
vector<bool> marc(n);
while(!fila.empty()){
int a=fila.front();fila.pop();
if(marc[a])continue;
auto p=query(a-k+1,a-1);
if(p.first==0)continue;
ord.push_back(a);
marc[a]=1;
update(a-k+1,a-1,-1);
if(p.first==1){
fila.push(p.second);
}
update(a,a,MOD);
}
set<int> s;
for(auto a:ord){
s.insert(a);
auto pt=s.find(a);
pt++;
rig[0][a]=lef[0][a]=a;
if(pt==s.end()){
auto ptaux=s.begin();
int x=*ptaux;
if(x+n-a<k)rig[0][a]=x;
}else{
int x=*pt;
if(x-a<k)rig[0][a]=x;
}
pt--;
if(pt==s.begin()){
auto ptaux=s.end();
ptaux--;
int x=*ptaux;
if(a+n-x<k)lef[0][a]=x;
}
else{
pt--;
int x=*pt;
if(a-x<k)lef[0][a]=x;
}
}
L(j,1,LG-1){
L(i,0,n-1){
lef[j][i]=lef[j-1][lef[j-1][i]];
rig[j][i]=rig[j-1][rig[j-1][i]];
}
}
}
int compare_plants(int x, int y) {
if(pulal(x,y)||pular(x,y))return -1;
else if(pulal(y,x)||pular(y,x))return 1;
return 0;
}
