#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, maxN = 8e5 + 5, lg = 18, INF = 1e6;
int n, k;
int a[maxn];
pair<int,int> seg[maxN][2];
int lazy[maxN][2];
void build(int id, int l, int r, int j) {
lazy[id][j] = 0;
if (l == r) {
if (j == 0) seg[id][j] = {a[l], l};
else seg[id][j] = {-INF, l};
return;
}
int mid = (l+r)/2;
build(id*2, l, mid, j); build(id*2+1, mid+1, r, j);
seg[id][j] = max(seg[id*2][j], seg[id*2+1][j]);
}
void push(int id, int j) {
seg[id][j].first += lazy[id][j];
if (id*2 < maxN) lazy[id*2][j] += lazy[id][j];
if (id*2+1 < maxN) lazy[id*2+1][j] += lazy[id][j];
lazy[id][j] = 0;
}
void upd(int id, int l, int r, int findl, int findr, int val, int j) {
push(id, j);
if (r < findl || findr < l) return;
if (findl <= l && r <= findr) {
lazy[id][j] += val;
push(id, j);
return;
}
int mid = (l+r)/2;
upd(id*2, l, mid, findl, findr, val, j); upd(id*2+1, mid+1, r, findl, findr, val, j);
seg[id][j] = max(seg[id*2][j], seg[id*2+1][j]);
}
pair<int,int> mx(int id, int l, int r, int findl, int findr, int j) {
push(id, j);
if (r < findl || findr<l) return {-INF, -1};
if (findl <= l && r <= findr) return seg[id][j];
int mid = (l+r)/2;
return max(mx(id*2, l, mid, findl, findr, j), mx(id*2+1, mid+1, r, findl, findr, j));
}
pair<int,int> qry(int l, int r, int j) {
l = (l + n) % n, r = (r + n) % n;
if (l <= r) return mx(1, 0, n-1, l, r, j);
return max(mx(1, 0, n-1, l, n-1, j), mx(1, 0, n-1, 0, r, j));
}
void update(int l, int r, int val, int j) {
l = (l + n) % n, r = (r + n) % n;
if (l <= r) upd(1, 0, n-1, l, r, val, j);
else {
upd(1, 0, n-1, l, n-1, val, j);
upd(1, 0, n-1, 0, r, val, j);
}
}
int ord[maxn], pos[maxn], L[maxn][lg], R[maxn][lg];
void init(int K, std::vector<int> r) {
n = r.size(), k = K;
for (int i=0;i<n;i++) a[i] = r[i];
build(1, 0, n-1, 0); build(1, 0, n-1, 1);
for (int i=0;i<n;i++) {
pair<int,int> add = qry(0, n-1, 0);
while (add.first == k-1) {
int u = add.second;
// cout << i << " " << add.first << " " << add.second << endl;
update(u, u, -INF, 0);
update(u, u, INF, 1);
update(u+1, u+k-1, -1, 1);
add = qry(0, n-1, 0);
}
int nw = qry(0, n-1, 1).second;
ord[nw] = i;
pos[i] = nw;
// cout << nw << endl;
update(nw, nw, -INF, 1);
update(nw+1, nw+k-1, 1, 1);
update(nw-k+1, nw-1, 1, 0);
}
// for (int i=0;i<n;i++) cout << ord[i] << " "; cout << endl;
build(1, 0, n-1, 1);
for (int i=0;i<n;i++) {
int cur = pos[i];
L[cur][0] = R[cur][0] = INF;
pair<int,int> val = qry(cur-k+1, cur-1, 1);
if (val.first >= 0) L[cur][0] = (cur - val.second + n) % n;
val = qry(cur+1, cur+k-1, 1);
if (val.first >= 0) R[cur][0] = (val.second - cur + n) % n;
update(cur, cur, i + INF, 1);
// cout << cur << " " << L[cur] << " " << R[cur] << endl;
}
for (int i=1;i<lg;i++) {
for (int j=0;j<n;j++) {
L[j][i] = L[j][i-1] + L[(j - L[j][i-1] + n) % n][i-1];
R[j][i] = R[j][i-1] + R[(j + R[j][i-1]) % n][i-1];
}
}
// cout << "test\n";
// for (int i=0;i<n;i++) cout << qry(i, i, 1).second << " "; cout << endl;
}
int compare_plants(int x, int y) {
int ans = 1;
if (ord[x] < ord[y]) swap(x, y), ans = -1;
if ((y - x + n) % n > k-1) {
int target = ((y - k) - x + n) % n, u = x, cur = 0;
for (int i=lg-1;i>=0;i--) {
if (cur + R[u][i] <= target) cur += R[u][i], x = (x + R[u][i]) % n;
}
if (R[u][0] != INF) {
u = (u + R[u][0]) % n;
if (ord[u] > ord[y]) return ans;
}
} else {
if (ord[x] > ord[y]) return ans;
}
if ((x - y + n) % n > k-1) {
int target = (x - (y + k) + n) % n, u = x, cur = 0;
for (int i=lg-1;i>=0;i--) {
if (cur + L[u][i] <= target) cur += L[u][i], x = (x - L[u][i] + n) % n;
}
if (L[u][0] != INF) {
u = (u - L[u][0] + n) % n;
if (ord[u] > ord[y]) return ans;
}
} else {
if (ord[x] > ord[y]) return ans;
}
return 0;
}
