#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=1,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);
if(seg[id<<1] != 0) return qryfull(id<<1|1,tm+1,tr);
else return qryfull(id<<1,tl,tm);
}
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]);
set<int> lst,vld;
int temp = N;
auto Check = [&](int x){
x %= N;
if(lst.empty()) return true;
int tx = *prev(lst.lower_bound(x+N));
if(x+N-tx < K) return false;
return true;
};
while(temp--){
while(true){
int id = qryfull(1,0,N-1);
if(id == -1) break;
upd(1,0,N-1,id,id,inf);
if(Check(id)) vld.insert(id);
lst.insert(id);
lst.insert(N+id);
if(!lst.empty() && !Check(*(lst.upper_bound(id)))) vld.erase((*(lst.upper_bound(id)))%N);
}
int target = *(vld.begin());
rev[indexing] = target;
arr[target] = indexing++;
if(target > 0) upd(1,0,N-1,max(0,target-K+1),target-1,-1);
if(0 > target-K+1) upd(1,0,N-1,N+target-K+1,N-1,-1);
vld.erase(target);
lst.erase(target);
lst.erase(target+N);
if(!lst.empty() && Check(*(lst.upper_bound(target)))) vld.insert((*(lst.upper_bound(target)))%N);
}
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 <= sr[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;
}
