#include "plants.h"
#include <bits/stdc++.h>
#define ent '\n'
const int maxn = 5e5 + 12;
using namespace std;
int r[maxn], a[maxn];
pair<int, int> t[maxn * 4];
int p[maxn * 4];
int del[maxn], add[maxn];
int n, k;
void build(int v, int tl, int tr) {
if(tl == tr) {
t[v] = {r[tl], tl};
return;
}
int mid = (tl + tr) >> 1;
build(v * 2, tl, mid);
build(v * 2 + 1, mid + 1, tr);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
void push(int v, int tl, int tr) {
if(tl == tr) return;
t[v * 2].first += p[v];
t[v * 2 + 1].first += p[v];
p[v * 2] += p[v], p[v * 2 + 1] += p[v];
p[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, int x) {
if(tl > r || l > tr) return;
if(tl >= l && tr <= r) {
t[v].first += x;
p[v] += x;
return;
}
push(v, tl, tr);
int mid = (tl + tr) >> 1;
upd(v * 2, tl, mid, l, r, x);
upd(v * 2 + 1, mid + 1, tr, l, r, x);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
void upd(int l, int r, int x) {
l %= n, r %= n;
if(l < 0) l += n;
if(r < 0) r += n;
if(l <= r) {
upd(1, 0, n - 1, l, r, x);
}
else {
upd(1, 0, n - 1, l, n - 1, x);
upd(1, 0, n - 1, 0, r, x);
}
}
pair<int, int> get(int v, int tl, int tr, int l, int r) {
if(tl > r || l > tr) return {1e9, 0};
if(tl >= l && tr <= r) return t[v];
push(v, tl, tr);
int mid = (tl + tr) >> 1;
return min(get(v * 2, tl, mid, l, r), get(v * 2 + 1, mid + 1, tr, l, r));
}
pair<int, int> get(int l, int r) {
l %= n, r %= n;
if(l < 0) l += n;
if(r < 0) r += n;
if(l <= r) {
return get(1, 0, n - 1, l, r);
}
return min(get(1, 0, n - 1, l, n - 1), get(1, 0, n - 1, 0, r));
}
int pl[maxn], pr[maxn];
int position[maxn];
void apply(int pos, int &_) {
while(get(pos - k + 1 , pos - 1).first == 0) {
apply(get(pos - k + 1 , pos - 1).second, _);
}
a[pos] = --_;
position[a[pos]] = pos;
upd(pos, pos, 1e9);
upd(pos - k + 1, pos - 1, -1);
}
int upl[20][maxn], upr[20][maxn];
int sl[20][maxn], sr[20][maxn];
void init(int K, std::vector<int> R) {
k = K;
n = (int)R.size();
for(int i = 0; i < n; i++) {
r[i] = R[i];
}
build(1, 0, n - 1);
int _ = n;
while(_ > 0) {
apply(t[1].second, _);
}
for(int i = 0; i < n; i++) {
upd(i, i, -get(i, i).first);
upd(i, i, 1e9);
}
for(int j = 0; j < n; j++) {
int i = position[j];
auto [lval, le] = get(i - k + 1, i);
auto [rval, ri] = get(i, i + k - 1);
pl[i] = pr[i] = -1;
if(lval <= 0) pl[i] = le;
if(rval <= 0) pr[i] = ri;
upd(i, i, -a[i] - get(i, i).first);
}
auto len = [&](int l, int r) -> int {
if(l <= r) return r - l;
return r + n - l;
};
for(int i = 0; i < n; i++) {
upl[0][i] = pl[i];
sl[0][i] = len(pl[i], i);
upr[0][i] = pr[i];
sr[0][i] = len(i, pr[i]);
}
for(int k = 1; k < 20; k++) {
for(int i = 0; i < n; i++) {
if(upl[k - 1][i] == -1) {
upl[k][i] = -1;
sl[k][i] = sl[k - 1][i];
}
else {
upl[k][i] = upl[k - 1][upl[k - 1][i]];
sl[k][i] = sl[k - 1][upl[k - 1][i]] + sl[k - 1][i];
}
if(upr[k - 1][i] == -1) {
upr[k][i] = -1;
sr[k][i] = sr[k - 1][i];
}
else {
upr[k][i] = upr[k - 1][upr[k - 1][i]];
sr[k][i] = sr[k - 1][i] + sr[k - 1][upr[k - 1][i]];
}
}
}
}
bool check(int l, int r, int x) {
l %= n, r %= n;
if(l < 0) l += n;
if(r < 0) r += n;
if(l <= r) return (l <= x && x <= r);
return (x <= r || x >= l);
}
bool check(int x, int y) {
int z = x, len = 1;
for(int i = 19; i >= 0; i--) {
if(upr[i][z] != -1 && !check(x, upr[i][z], y) && len + sr[i][z] < n) {
len += sr[i][z];
z = upr[i][z];
}
}
assert(z != y);
if(upr[0][z] != -1 && (check(x, upr[0][z], y) || len + sr[0][z] >= n) && a[z] > a[y]) {
return true;
}
z = x, len = 1;
for(int i = 19; i >= 0; i--) {
if(upl[i][z] != -1 && !check(upl[i][z], x, y) && len + sl[i][z] < n) {
len += sl[i][z];
z = upl[i][z];
}
}
assert(z != y);
if(upl[0][z] != -1 && (check(upl[0][z], x, y) || len + sl[0][z] >= n) && a[z] > a[y]) {
return true;
}
return false;
}
int compare_plants(int x, int y) {
if(check(y, x)) return -1;
if(check(x, y)) return 1;
return 0;
}
