#include "plants.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
vector<int> rk;
struct ST{
struct no{
pair<int,int> mn;
int tag=0;
};
vector<no> st;
void init(int x){
st.resize(4*x);
}
void build(int v,int L,int R,vector<int>& a){
if(L==R){
st[v].mn={a[L],L};
return;
}
int m=(L+R)/2;
build(2*v+1,L,m,a);
build(2*v+2,m+1,R,a);
st[v].mn=min(st[2*v+1].mn,st[2*v+2].mn);
}
void upd(int v,int t){
st[v].tag+=t;
st[v].mn.fs+=t;
}
void pudo(int v){
if(st[v].tag==0){
return;
}
upd(2*v+1,st[v].tag);
upd(2*v+2,st[v].tag);
st[v].tag=0;
}
void update(int v,int L,int R,int l,int r,int t){
if(l==L && r==R){
upd(v,t);
return;
}
pudo(v);
int m=(L+R)/2;
if(r<=m){
update(2*v+1,L,m,l,r,t);
}
else if(l>m){
update(2*v+2,m+1,R,l,r,t);
}
else{
update(2*v+1,L,m,l,m,t);
update(2*v+2,m+1,R,m+1,r,t);
}
st[v].mn=min(st[2*v+1].mn,st[2*v+2].mn);
}
pair<int,int> query(int v,int L,int R,int l,int r){
if(L==l && r==R){
return st[v].mn;
}
pudo(v);
int m=(L+R)/2;
if(r<=m){
return query(2*v+1,L,m,l,r);
}
else if(l>m){
return query(2*v+2,m+1,R,l,r);
}
else{
return min(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
}
}
}st;
int n,k;
set<int> s,ab;
vector<bitset<200005> > bt;
vector<vector<int> > e;
void add(int x){
if(!s.size()){
s.insert(x);
ab.insert(x);
return;
}
auto a=s.lower_bound(x);
auto b=a;
if(a==s.end()){
a=s.begin();
}
if(a==s.begin()){
b=prev(s.end());
}
else{
b=prev(a);
}
if((x-(*b)+n)%n>=k){
ab.insert(x);
}
else{
e[*b].push_back(x);
e[*b][x]=1;
}
if(((*a)-x+n)%n<k){
e[x].push_back(*a);
bt[x][*a]=1;
ab.erase(*a);
}
s.insert(x);
}
void del(int x){
ab.erase(x);
s.erase(x);
if(!s.size()){
return;
}
auto a=s.lower_bound(x);
auto b=a;
if(a==s.end()){
a=s.begin();
}
if(a==s.begin()){
b=prev(s.end());
}
else{
b=prev(a);
}
ab.insert(*a);
}
void update(int l,int r){
int f=(r+1)%n;
if(l>r){
st.update(0,0,n-1,l,n-1,-1);
st.update(0,0,n-1,0,r,-1);
while(1){
auto h=st.query(0,0,n-1,0,r);
if(h.fs>0){
break;
}
e[f].push_back(h.sc);
bt[f][h.sc]=1;
add(h.sc);
st.update(0,0,n-1,h.sc,h.sc,10000008);
}
while(1){
auto h=st.query(0,0,n-1,l,n-1);
if(h.fs>0){
break;
}
e[f].push_back(h.sc);
bt[f][h.sc]=1;
add(h.sc);
st.update(0,0,n-1,h.sc,h.sc,10000008);
}
}
else{
st.update(0,0,n-1,l,r,-1);
while(1){
auto h=st.query(0,0,n-1,l,r);
if(h.fs>0){
break;
}
bt[f][h.sc]=1;
e[f].push_back(h.sc);
add(h.sc);
st.update(0,0,n-1,h.sc,h.sc,10000008);
}
}
}
void init(int K, vector<int> r) {
n=r.size();
e.resize(n);
bt.resize(n);
for(int i=0;i<n;i++){
bt[i][i]=1;
}
k=K;
rk.resize(n);
st.init(n);
st.build(0,0,n-1,r);
for(int i=0;i<n;i++){
if(r[i]==0){
add(i);
st.update(0,0,n-1,i,i,10000007);
}
}
vector<int> z;
for(int i=0;i<n;i++){
auto h=*ab.begin();
auto xl=(h+1-k+n)%n;
auto xr=(h-1+n)%n;
rk[h]=i;
z.push_back(i);
del(h);
update(xl,xr);
}
for(int i=n-1;i>=0;i--){
for(auto h:e[z[i]]){
bt[z[i]]|=bt[h];
}
}
return;
}
int compare_plants(int x, int y) {
if(bt[x][y]){
return 1;
}
else if(bt[y][x]){
return -1;
}
else{
return 0;
}
}
