#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, maxN = 8e5 + 5, 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], R[maxn];;
int dp[305][305];
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] = R[cur] = -1;
pair<int,int> val = qry(cur-k+1, cur-1, 1);
if (val.first >= 0) L[cur] = val.second;
val = qry(cur+1, cur+k-1, 1);
if (val.first >= 0) R[cur] = val.second;
update(cur, cur, cur + INF, 1);
// cout << cur << " " << L[cur] << " " << R[cur] << endl;
}
for (int i=0;i<n;i++) {
for (int j=1;j<=k-1;j++) {
int J = (i+j)%n;
if (ord[i] > ord[J]) dp[i][J] = 1, dp[J][i] = -1;
else dp[i][J] = -1, dp[J][i] = 1;
}
}
// for (int i=0;i<n;i++) {
// for (int j=0;j<n;j++) cout << dp[i][j] << " "; cout << endl;
// }
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) for (int k=0;k<n;k++) {
if (dp[j][i] == dp[i][k] && dp[i][k] != 0) dp[j][k] = dp[j][i];
}
}
// for (int i=0;i<n;i++) cout << qry(i, i, 1).second << " "; cout << endl;
}
int compare_plants(int x, int y) {
return dp[x][y];
int ans = 1;
if (ord[x] < ord[y]) swap(x, y), ans = -1;
int cur = x;
bool dead = false;
while ((y - cur + n)%n > k-1) {
if (R[cur] == -1) {
dead = true;
break;
}
cur = R[cur];
}
if (!dead && ord[cur] >= ord[y]) return ans;
// cout << x << " " << y << endl;
cur = x, dead = false;
// cout << cur << " " << y << endl;
while ((cur - y + n)%n > k-1) {
if (L[cur] == -1) {
dead = true;
break;
}
cur = L[cur];
}
// cout << x << " " << y << " " << cur << " " << dead << endl;
if (!dead && ord[cur] >= ord[y]) return ans;
return 0;
}
