#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;
int maxb,h[maxn],nx[maxn][20],pv[maxn][20],dnx[maxn][20],dpv[maxn][20];
stack<int> st;
set<ii> s;
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]);
}
while(cnt>=0){
if(st.empty()){
st.push((root->qry(0,n-1)).se);
}
int cur=st.top();
ii pr=root->qry2(sub(cur,k-1),sub(cur,1));
if(pr.fi==0){
st.push(pr.se);continue;
}
h[cur]=cnt--;
root->up(cur,cur,maxn);
root->up2(sub(cur,k-1),sub(cur,1),-1);
st.pop();
}
memset(pv,-1,sizeof pv);
memset(nx,-1,sizeof nx);
for(int i=0;i<k-1;++i)s.insert({h[i],i});
for(int i=n-1;i>=0;--i){
auto it=s.upper_bound({h[i],0});
if(it!=s.end()){
nx[i][0]=(*it).se;
dnx[i][0]=sub(nx[i][0],i);
}
s.erase(s.find({h[add(i,k-1)],add(i,k-1)}));
s.insert({h[i],i});
}
s.clear();
for(int i=sub(n,k-1);i<n;++i)s.insert({h[i],i});
for(int i=0;i<n;++i){
auto it=s.upper_bound({h[i],0});
if(it!=s.end()){
pv[i][0]=(*it).se;
dpv[i][0]=sub(i,pv[i][0]);
}
s.erase(s.find({h[sub(i,k-1)],sub(i,k-1)}));
s.insert({h[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&&dnx[i][j-1]+dnx[nx[i][j-1]][j-1]<=n){
nx[i][j]=nx[nx[i][j-1]][j-1];
dnx[i][j]=dnx[i][j-1]+dnx[nx[i][j-1]][j-1];
}
if(pv[i][j-1]!=-1&&dpv[i][j-1]+dpv[pv[i][j-1]][j-1]<=n){
pv[i][j]=pv[pv[i][j-1]][j-1];
dpv[i][j]=dpv[i][j-1]+dpv[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(sub(y,t)+sub(t,x)==sub(y,x)&&h[t]<=h[y])x=t;
}
if(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(sub(x,t)+sub(t,y)==sub(x,y)&&h[t]<=h[y])x=t;
}
if(sub(x,y)<k)return true;
return false;
}
int compare_plants(int x,int y){
int ans=-1;
if(h[x]>h[y])ans=1,swap(x,y);
if(!check(x,y))ans=0;
return ans;
}
