#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pf printf
#define pb push_back
typedef pair<int,int> ii;
#define maxn 200005
int n,k;
inline int add(int a,int b){return (a+b)%n;}
inline int sub(int a,int b){return (a-b+n)%n;}
struct node{
int s,e,m,lz;ii v;
node *l,*r;
node(int _s,int _e){
s=_s;e=_e;m=(s+e)/2;lz=0;v={0,s};
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void ppo(){
v.fi+=lz;
if(lz!=0&&s!=e)l->lz+=lz,r->lz+=lz;
lz=0;
}
void up(int x,int y,int nv){
if(s==x&&e==y){lz+=nv;return;}
if(y<=m)l->up(x,y,nv);
else if(x>m)r->up(x,y,nv);
else l->up(x,m,nv),r->up(m+1,y,nv);
l->ppo();r->ppo();v=min(l->v,r->v);
}
ii qry(int x,int y){
ppo();
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return min(l->qry(x,m),r->qry(m+1,y));
}
void up2(int x,int y,int nv){
if(x<=y)up(x,y,nv);
else up(0,y,nv),up(x,n-1,nv);
}
ii qry2(int x,int y){
if(x<=y)return qry(x,y);
else return min(qry(0,y),qry(x,n-1));
}
}*root;
struct node2{
int s,e,m,mn,mx;
node2 *l,*r;
node2(int _s,int _e){
s=_s;e=_e;m=(s+e)/2;mn=maxn;mx=-maxn;
if(s!=e)l=new node2(s,m),r=new node2(m+1,e);
}
void up(int x,int nv){
if(s==x&&e==x){mn=mx=nv;return;}
if(x<=m)l->up(x,nv);
else r->up(x,nv);
mn=min(l->mn,r->mn);
mx=max(l->mx,r->mx);
}
int qmn(int x,int y){
if(s==x&&e==y)return mn;
if(y<=m)return l->qmn(x,y);
if(x>m)return r->qmn(x,y);
return min(l->qmn(x,m),r->qmn(m+1,y));
}
int qmx(int x,int y){
if(s==x&&e==y)return mx;
if(y<=m)return l->qmx(x,y);
if(x>m)return r->qmx(x,y);
return max(l->qmx(x,m),r->qmx(m+1,y));
}
int qmn2(int x,int y){
if(x<=y)return qmn(x,y);
else{
int t=qmn(x,n-1);
if(t!=maxn)return t;
else return qmn(0,y);
}
}
int qmx2(int x,int y){
if(x<=y)return qmx(x,y);
else{
int t=qmx(0,y);
if(t!=-maxn)return t;
else return qmx(x,n-1);
}
}
}*root2;
int maxb,h[maxn],nx[maxn][20],pv[maxn][20];
bool done[maxn];
vector<int> z;
stack<int> st;
deque<ii> dq;
void init(int _k,vector<int> r){
n=r.size();k=_k;
root=new node(0,n-1);
int cnt=n-1;
for(int i=0;i<n;++i){
root->up(i,i,r[i]);
if(r[i]==0){
z.pb(i);
}
}
while(!z.empty()){
int cur=z.back();z.pop_back();
if(done[cur])continue;
while(true){
ii res=(root->qry2(sub(cur,k-1),sub(cur,1)));
st.push(cur);done[cur]=true;
if(res.fi==0)cur=res.se;
else break;
}
while(!st.empty()){
cur=st.top();st.pop();
int a=sub(cur,k-1),b=sub(cur,1);
ii res=root->qry2(a,b);
if(res.fi==0){
st.push(cur);
break;
}
h[cur]=cnt--;
root->up2(a,b,-1);
root->up(cur,cur,maxn);
while(true){
ii res=root->qry2(a,b);
if(res.fi==0){
z.pb(res.se);
root->up(res.se,res.se,maxn);
}
else break;
}
}
}
memset(pv,-1,sizeof pv);
memset(nx,-1,sizeof nx);
root2=new node2(0,n-1);
vector<ii> srt;
for(int i=0;i<n;++i)srt.pb({h[i],i});
sort(srt.begin(),srt.end(),greater<ii>());
for(ii pr:srt){
int i=pr.se;
int t=root2->qmn2(sub(i,k-1),sub(i,1));
if(t!=maxn)pv[i][0]=t;
t=root2->qmx2(add(i,1),add(i,k-1));
if(t!=-maxn)nx[i][0]=t;
root2->up(i,i);
}
for(int j=1;(1<<j)<n;++j){
maxb=j;
for(int i=0;i<n;++i){
if(nx[i][j-1]!=-1)nx[i][j]=nx[nx[i][j-1]][j-1];
if(pv[i][j-1]!=-1)pv[i][j]=pv[pv[i][j-1]][j-1];
}
}
}
bool check(int x,int y){//is x<y
int tmp=x;
for(int i=maxb;i>=0;--i){
int t=nx[x][i];
if(t==-1)continue;
if(t!=y&&sub(y,t)+sub(t,x)==sub(y,x))x=t;
}
if(h[x]<h[y]&&sub(y,x)<=k)return true;
x=tmp;
for(int i=maxb;i>=0;--i){
int t=pv[x][i];
if(t==-1)continue;
if(t!=y&&sub(x,t)+sub(t,y)==sub(x,y))x=t;
}
if(h[x]<h[y]&&sub(x,y)<=k)return true;
return false;
}
int compare_plants(int x,int y){
bool a=check(x,y),b=check(y,x);
if(a==b)return 0;
if(a==1)return -1;
else return 1;
}
