#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 8;
const int mlog = 20;
const int inf = 1e9;
int N,K,seg[4*maxn],lazy[4*maxn],indexing=0,arr[maxn],rev[maxn],lf[mlog][maxn],sl[mlog][maxn],rg[mlog][maxn],sr[mlog][maxn];
void push(int id){
lazy[id<<1] += lazy[id];
lazy[id<<1|1] += lazy[id];
seg[id<<1] += lazy[id];
seg[id<<1|1] += lazy[id];
lazy[id] = 0;
}
void upd(int id,int tl,int tr,int ul,int ur,int v){
if(tl > tr || ul > tr || ur < tl) return;
if(ul <= tl && tr <= ur){
seg[id] += v;
lazy[id] += v;
return;
}
int tm = (tl+tr)/2;
push(id);
upd(id<<1,tl,tm,ul,ur,v);
upd(id<<1|1,tm+1,tr,ul,ur,v);
seg[id] = min(seg[id<<1],seg[id<<1|1]);
}
int qryfull(int id,int tl,int tr){
if(seg[id] != 0) return -1;
if(tl == tr) return tl;
int tm = (tl+tr)/2;
push(id);
int res = -1;
if(seg[id<<1] != 0) res = qryfull(id<<1|1,tm+1,tr);
else res = qryfull(id<<1,tl,tm);
seg[id] = min(seg[id<<1],seg[id<<1|1]);
return res;
}
int qrypart(int id,int tl,int tr,int ql){
if(tl == tr) return seg[id];
int tm = (tl+tr)/2;
push(id);
int res = -1;
if(tm < ql) res = qrypart(id<<1|1,tm+1,tr,ql);
else res = qrypart(id<<1,tl,tm,ql);
seg[id] = min(seg[id<<1],seg[id<<1|1]);
return res;
}
void rec(int x){
for(int i=1-K;i<0;i++) if(qrypart(1,0,N-1,(x+N+i)%N) == 0) rec((x+N+i)%N);
upd(1,0,N-1,x,x,inf);
if(x > 0) upd(1,0,N-1,max(0,x-K+1),x,-1);
if(0 > x-K+1) upd(1,0,N-1,N+x-K+1,N-1,-1);
rev[indexing] = x;
arr[x] = indexing++;
}
void init(int k, std::vector<int> r){
K = k;
N = r.size();
for(int i=0;i<N;i++) upd(1,0,N-1,i,i,r[i]);
while(qryfull(1,0,N-1) != -1) rec(qryfull(1,0,N-1));
set<int> st;
for(int i=1-K;i<0;i++) st.insert(arr[N+i]);
for(int i=0;i<N;i++){
auto it = st.lower_bound(arr[i]);
if(it == st.begin()) lf[0][i] = i;
else lf[0][i] = rev[*prev(it)];
sl[0][i] = (N+i-lf[0][i])%N;
st.insert(arr[i]);
st.erase(arr[(N+i-K+1)%N]);
}
st.clear();
for(int i=1;i<K;i++) st.insert(arr[i]);
for(int i=0;i<N;i++){
auto it = st.lower_bound(arr[i]);
if(it == st.begin()) rg[0][i] = i;
else rg[0][i] = rev[*prev(it)];
sr[0][i] = (N+rg[0][i]-i)%N;
st.insert(arr[(i+K)%N]);
st.erase(arr[(i+1)%N]);
}
st.clear();
for(int i=1;i<mlog;i++){
for(int j=0;j<N;j++){
lf[i][j] = lf[i-1][lf[i-1][j]];
sl[i][j] = sl[i-1][j]+sl[i-1][lf[i-1][j]];
rg[i][j] = rg[i-1][rg[i-1][j]];
sr[i][j] = sr[i-1][j]+sr[i-1][rg[i-1][j]];
}
}
}
bool comp(int x,int y){
int tx = x;
int dx = (N+x-y)%N;
for(int i=mlog-1;i>=0;i--){
if(sl[i][tx] <= dx){
dx -= sl[i][tx];
tx = lf[i][tx];
}
}
int ty = x;
int dy = (N+y-x)%N;
for(int i=mlog-1;i>=0;i--){
if(sr[i][ty] <= dy){
dy -= sr[i][ty];
ty = rg[i][ty];
}
}
if(dx <= sl[0][tx] && arr[y] >= arr[tx]) return true;
if(dy <= sl[0][ty] && arr[y] >= arr[ty]) return true;
return false;
}
int compare_plants(int x, int y){
bool a = comp(x,y);
if(a) return -1;
bool b = comp(y,x);
if(b) return 1;
return 0;
}
