#include "plants.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
int n;
struct Segtree{
pair<int, int> mn[800005];
int lz[800005];
void push(int id, int l, int r){
mn[id].ff += lz[id];
if(l != r){
lz[id << 1] += lz[id];
lz[id << 1 | 1] += lz[id];
}
lz[id] = 0;
}
void build(int id, int l, int r, vector<int>& v){
if(l == r){
mn[id] = {v[l], l};
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m, v);
build(id << 1 | 1, m + 1, r, v);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}
void update(int id, int l, int r, int L, int R, int x){
if(L <= l && r <= R){
lz[id] += x;
push(id, l, r);
return;
}
push(id, l, r);
if(l > R || r < L) return;
int m = (l + r) >> 1;
update(id << 1, l, m, L, R, x);
update(id << 1 | 1, m + 1, r, L, R, x);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}
pair<int, int> query(int id, int l, int r, int L, int R){
push(id, l, r);
if(l > R || r < L)
return {1'000'000, 1};
if(L <= l && r <= R)
return mn[id];
int m = (l + r) >> 1;
return min(query(id << 1, l, m, L, R), query(id << 1 | 1, m + 1, r, L, R));
}
} s, t;
int le[200005][20], ri[200005][20];
vector<int> q;
int h[200005];
bool cw(int x, int y, int z){
if(x <= y && y <= z)
return 1;
if(y <= z && z <= x)
return 1;
if(z <= x && x <= y)
return 1;
return 0;
}
int k;
void init(int k, std::vector<int> v) {
n = v.size();
--k;
::k = k;
for(auto& x : v)
x = k - x;
s.build(1, 0, n - 1, v);
for(auto& x : v)
x = 0;
t.build(1, 0, n - 1, v);
for(int i = 0; i < n; ++i)
for(int j = 0; j < 20; ++j)
ri[i][j] = le[i][j] = -1;
for(int i = 1; i <= n; ++i){
int now;
if(q.empty())
now = s.query(1, 0, n - 1, 0, n - 1).ss;
else {
now = q.back();
q.pop_back();
}
pair<int, int> tmp = min(s.query(1, 0, n - 1, now - k, now - 1), s.query(1, 0, n - 1, now - k + n, n - 1));
while(tmp.ff == 0){
q.push_back(now);
now = tmp.ss;
tmp = min(s.query(1, 0, n - 1, now - k, now - 1), s.query(1, 0, n - 1, now - k + n, n - 1));
}
s.update(1, 0, n - 1, now, now, 800'005);
s.update(1, 0, n - 1, now - k, now - 1, -1);
s.update(1, 0, n - 1, now - k + n, n - 1, -1);
h[now] = i;
tmp = min(t.query(1, 0, n - 1, now - k, now - 1), t.query(1, 0, n - 1, now - k + n, n - 1));
le[now][0] = tmp.ff == 0 ? -1 : tmp.ss;
tmp = min(t.query(1, 0, n - 1, now + 1, now + k), t.query(1, 0, n - 1, 0, now + k - n));
ri[now][0] = tmp.ff == 0 ? -1 : tmp.ss;
for(int i = 0; le[now][i] != -1; ++i){
le[now][i + 1] = le[le[now][i]][i];
if(le[now][i + 1] != -1 && cw(le[now][0], le[now][i + 1], now))
le[now][i + 1] = -1;
}
for(int i = 0; ri[now][i] != -1; ++i){
ri[now][i + 1] = ri[ri[now][i]][i];
if(ri[now][i + 1] != -1 && cw(now, ri[now][i + 1], ri[now][0]))
ri[now][i + 1] = -1;
}
t.update(1, 0, n - 1, now, now, -i);
}
}
int compare_plants(int x, int y){
if(h[x] > h[y]) return -compare_plants(y, x);
int ry = y, ly = y;
for(int i = 19; i >= 0; --i)
if(ri[ry][i] != -1 && cw(y, ri[ry][i], x))
ry = ri[ry][i];
if(min(abs(ry - x), n - abs(ry - x)) <= k)
return -1;
for(int i = 19; i >= 0; --i)
if(le[ly][i] != -1 && cw(x, le[ly][i], y))
ly = le[ly][i];
if(min(abs(ly - x), n - abs(ly - x)) <= k)
return -1;
return 0;
}
