#include "plants.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 2e5+5, LOG = 18;
int N, K, T, H[MAXN], L[MAXN][LOG], R[MAXN][LOG];
vector <int> A = {0};
set <pii> S;
struct tree {
int L, R, val, lz;
tree *lef, *rig;
tree(int x,int y) {
L = x; R = y;
lz = 0;
if (L == R) {
val = A[L];
return;
}
int mid=(L+R)/2;
lef = new tree(L,mid);
rig = new tree(mid+1,R);
val = min(lef->val,rig->val);
}
void push() {
if (lz) {
lef->val -= lz;
lef->lz += lz;
rig->val -= lz;
rig->lz += lz;
lz = 0;
}
}
int find(int x,int y) {
if (x > R || y < L || val) {
return -1;
}
if (L == R) {
return L;
}
push();
int res = lef->find(x,y);
if (res != -1) {
return res;
}
return rig->find(x,y);
}
void update(int x,int y) {
if (x > R || y < L) {
return;
}
if (x <= L && y >= R) {
val--;
lz++;
return;
}
push();
lef->update(x,y);
rig->update(x,y);
val = min(lef->val,rig->val);
}
void del(int x) {
if (L == R) {
val = MAXN;
return;
}
push();
int mid = (L+R)/2;
if (x <= mid) {
lef->del(x);
}
else {
rig->del(x);
}
val = min(lef->val,rig->val);
}
} root(0,0);
void dfs(int x) {
while (1) {
int y = root.find(x-K+1,x-1);
if (y == -1) {
break;
}
dfs(y);
}
while (1) {
int y = root.find(x+N-K+1,N-1);
if (y == -1) {
break;
}
dfs(y);
}
H[x] = T;
T--;
root.del(x);
root.update(x-K+1,x-1);
root.update(x+N-K+1,N-1);
}
void init(int k,vector<int> r) {
K = k;
A = r;
T = N = A.size();
root = tree(0,N-1);
while (T) {
int x = root.find(0,N-1);
dfs(x);
}
for (int i=0;i<K-1;i++) {
S.insert({H[i],i});
}
for (int i=0;i<N;i++) {
S.erase({H[i],i});
S.insert({H[(i+K-1)%N],(i+K-1)%N});
auto it = S.lower_bound({H[i],0});
if (it != S.begin()) {
it--;
R[i][0] = (it->se - i + N) % N;
}
it = S.lower_bound({H[(i+K)%N],0});
if (it != S.begin()) {
it--;
L[(i+K)%N][0] = (i + K - it->se + N) % N;
}
}
for (int i=1;i<LOG;i++) {
for (int j=0;j<=N;j++) {
L[j][i] = min(N, L[j][i-1] + L[(j-L[j][i-1]+N)%N][i-1]);
R[j][i] = min(N, R[j][i-1] + R[(j+R[j][i-1])%N][i-1]);
}
}
}
bool taller(int x,int y) {
int z = x;
for (int i=LOG-1;i>=0;i--) {
if (L[z][i] < (z-y+N)%N) {
z = (z-L[z][i]+N)%N;
}
}
if ((z-y+N)%N < K && H[z] > H[y]) {
return 1;
}
z = x;
for (int i=LOG-1;i>=0;i--) {
if (R[z][i] < (y-z+N)%N) {
z = (z+R[z][i])%N;
}
}
if ((y-z+N)%N < K && H[z] > H[y]) {
return 1;
}
return 0;
}
int compare_plants(int x,int y) {
if (taller(x,y)) {
return 1;
}
if (taller(y,x)) {
return -1;
}
return 0;
}
