#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
struct lazy_segtree {
vector<pair<int,int>> T;
vector<int> lz;
int n;
void build(vector<int> &a, int tl, int tr, int v) {
if(tl == tr) {
T[v] = {a[tl], tl};
return;
}
int tm = (tl+tr)/2;
build(a, tl, tm, 2*v);
build(a, tm+1, tr, 2*v+1);
T[v] = min(T[2*v], T[2*v+1]);
}
lazy_segtree(vector<int> &a) {
n=a.size();
T.resize(4*n);
lz.resize(4*n);
build(a, 0, n-1, 1);
}
void push(int v){
lz[2*v] += lz[v];
lz[2*v+1] += lz[v];
T[2*v].first += lz[v];
T[2*v+1].first += lz[v];
lz[v] = 0;
}
void update(int l, int r, int add, int tl, int tr, int v) {
if(r < tl or tr < l)return;
if(l <= tl and tr<=r) {
lz[v]+=add;
T[v].first+=add;
return;
}
push(v);
int tm=(tl+tr)/2;
update(l, r, add, tl, tm, 2*v);
update(l, r, add, tm+1, tr, 2*v+1);
T[v] = min(T[2*v], T[2*v+1]);
}
pair<int,int> query(int l, int r, int tl, int tr, int v) {
if(r < tl or tr < l)return {1e9, 1e9};
if(l <= tl and tr<=r)return T[v];
push(v);
int tm=(tl+tr)/2;
return min(query(l, r, tl, tm, 2*v), query(l, r, tm+1, tr, 2*v+1));
}
void update(int l, int r, int add) {
update(l, r, add, 0, n-1, 1);
}
pair<int,int> query(int l, int r) {
return query(l, r, 0, n-1, 1);
}
};
const int N = 4e5+10;
vector<int> H;
vector<int> g[N];
const int lg = 20;
int sml[N][lg], grt[N][lg];
int k;
int n;
void init(int K, std::vector<int> r) {
k=K;
n = r.size();
lazy_segtree ls(r);
int cnt = n;
H.resize(n, -1);
auto dfs = [&](int at, auto &&dfs) -> void {
if(at >= k-1) {
pair<int,int> val = ls.query(at-k+1, at-1);
while(val.first == 0) {
dfs(val.second, dfs);
val = ls.query(at-k+1, at-1);
}
H[at] = cnt--;
ls.update(at-k+1, at-1, -1);
ls.update(at, at, 1e9);
}
else {
pair<int,int> val = min(ls.query(0, at-1), ls.query(n-k+at+1, n-1));
while(val.first == 0) {
dfs(val.second, dfs);
val = min(ls.query(0, at-1), ls.query(n-k+at+1, n-1));
}
H[at] = cnt--;
ls.update(0, at-1, -1), ls.update(n-k+at+1, n-1, -1);
ls.update(at, at, 1e9);
}
};
while(ls.query(0, n-1).first == 0) {
dfs(ls.query(0, n-1).second, dfs);
}
for(int i = 0;i<n;i++) {
H.push_back(H[i]);
}
// for(int i =0 ;i<2*n;i++) {
// int nxtmn = -1;
// for(int j = i+1;j<min(2*n, i+k);j++) {
// if(H[j] < H[i] and (nxtmn == -1 or H[nxtmn] < H[j])) {
// nxtmn = j;
// }
// }
// sml[i][0] = nxtmn;
// nxtmn = -1;
// for(int j = i+1;j<min(2*n, i+k);j++) {
// if(H[j] > H[i] and (nxtmn == -1 or H[nxtmn] > H[j])) {
// nxtmn = j;
// }
// }
// grt[i][0] = nxtmn;
// }
set<pair<int,int>> s;
s.insert({-1e9, 2*n});
s.insert({1e9, 2*n});
for(int i = 2*n-1;i>=0;i--) {
if(i+k < 2*n) {
s.erase({H[i+k], i+k});
}
grt[i][0] = (*s.lower_bound(pair{H[i], i})).second;
sml[i][0] = (*(--s.lower_bound(pair{H[i], i}))).second;
s.insert({H[i], i});
}
for(int i =0 ;i<2*n;i++) {
if(grt[i][0] == -1)grt[i][0]=2*n;
if(sml[i][0] == -1)sml[i][0]=2*n;
}
sml[2*n][0] = grt[2*n][0] = 2*n;
for(int i = 1;i<lg;i++) {
for(int j = 0;j<=2*n;j++) {
sml[j][i] = sml[sml[j][i-1]][i-1];
grt[j][i] = grt[grt[j][i-1]][i-1];
}
}
return;
}
int dist(int a, int b) {
return min({abs(a-b), abs(a+n-b), abs(b+n-a)});
}
int compare_plants(int x, int y) {
{
int a = x, b = y;
if(b < a)b+=n;
if(a+k-1 < b) {
for(int i = lg-1;i>=0;i--) {
if(grt[a][i] + k - 1 < b) {
a=grt[a][i];
}
}
a=grt[a][0];
}
if(a!=2*n and H[a]<H[b])return -1;
a=x;
if(a+k-1 < b) {
for(int i = lg-1;i>=0;i--) {
if(sml[a][i] + k - 1 < b) {
a=sml[a][i];
}
}
a=sml[a][0];
}
if(a!=2*n and H[a]>H[b])return 1;
}
{
int a = y, b = x;
if(b<a)b+=n;
if(a+k-1 < b) {
for(int i = lg-1;i>=0;i--) {
if(grt[a][i] + k - 1 < b) {
a=grt[a][i];
}
}
a=grt[a][0];
}
if(a!=2*n and H[a]<H[b])return 1;
a=y;
if(a+k-1 < b) {
for(int i = lg-1;i>=0;i--) {
if(sml[a][i] + k - 1 < b) {
a=sml[a][i];
}
}
a=sml[a][0];
}
if(a!=2*n and H[a]>H[b])return -1;
}
return 0;
}
