#include "plants.h"
#include <bits/stdc++.h>
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;
const int INF = 1e9, SZ = 1 << 19;
ii operator+(const ii &a, const int b) {
return {a.fst + b, a.snd};
}
struct Node {
ii l, ans;
int tam, mini, r;
Node() { ans = ii{-INF, -1}, l = ii{0, -1}, tam = r = 0, mini = INF; }
Node(const int &val, const int &idx) { ans = l = {1, idx}, tam = 1, mini = val, r = 0; }
friend Node merge(const Node &a, const Node &b) {
Node c;
c.tam = a.tam + b.tam;
c.mini = min(a.mini, b.mini);
c.l = a.l, c.r = b.r;
if (a.mini == b.mini) {
c.ans = max({a.ans, b.ans, b.l+a.r});
} else if (a.mini < b.mini) {
c.r = a.r + b.tam;
c.ans = a.ans;
} else {
c.l = b.l + a.tam;
c.ans = max(c.l, b.ans);
}
return c;
}
};
Node st[2 * SZ];
int lazy[2 * SZ];
void pass(int u) {
if (u < SZ) {
lazy[2 * u] += lazy[u];
lazy[2 * u + 1] += lazy[u];
}
st[u].mini += lazy[u];
lazy[u] = 0;
}
void update(int s, int e, int v, int l = 0, int r = SZ, int u = 1) {
pass(u);
if (e <= l || r <= s) return;
if (s <= l && r <= e) {
lazy[u] = v;
return pass(u);
}
int m = (l + r) / 2;
update(s, e, v, l, m, 2 * u);
update(s, e, v, m, r, 2 * u + 1);
st[u] = merge(st[2 * u], st[2 * u + 1]);
}
const int MAX_N = 2e5 + 9;
const int MAX_K = 20;
int L[MAX_K][MAX_N], R[MAX_K][MAX_N];
ll distL[MAX_K][MAX_N], distR[MAX_K][MAX_N];
int N, K, h[MAX_N];
ii maxi[2 * SZ];
void updateMaxi(int p, int v) {
maxi[p += SZ].fst = v;
while (p /= 2) maxi[p] = max(maxi[2 * p], maxi[2 * p + 1]);
}
void chmax(ii &a, ii b) {
if (b > a) a = b;
}
ii queryMaxi(int l, int r) {
ii ret = {-INF, -1};
for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) {
if (l & 1) chmax(ret, maxi[l++]);
if (r & 1) chmax(ret, maxi[--r]);
}
return ret;
}
void init(int k, vector <int> r) {
const int n = sz(r);
N = n, K = k;
forn(i, 2 * n) st[i + SZ] = Node(r[i % n], i);
dforsn(i, 1, SZ) st[i] = merge(st[2 * i], st[2 * i + 1]);
vi order;
forn(i, n) {
auto [_, pos] = st[1].ans;
pos %= n;
order.pb(pos);
if (k <= pos) {
update(pos - k + 1, pos, -1);
} else {
update(0, pos, -1);
update(2 * n + pos - k + 1, 2 * n, -1);
}
update(pos - k + 1 + n, pos + n, -1);
update(pos, pos + 1, INF);
update(pos + n, pos + n + 1, INF);
h[pos] = n - i - 1;
}
reverse(all(order));
forn(i, 2 * SZ) maxi[i] = {-INF, i - SZ};
for (int pos : order) {
ii bestLeft = {-INF, -1}, bestRight = {-INF, -1};
if (k <= pos) {
chmax(bestLeft, queryMaxi(pos - k + 1, pos));
} else {
chmax(bestLeft, queryMaxi(0, pos));
chmax(bestLeft, queryMaxi(n + pos - k + 1, 2 * n));
}
if (pos < n - k + 1) {
chmax(bestRight, queryMaxi(pos + 1, pos + k));
} else {
chmax(bestRight, queryMaxi(pos + 1, n));
chmax(bestRight, queryMaxi(0, pos + k - n));
}
if (bestLeft.fst == -INF) bestLeft.snd = pos;
if (bestRight.fst == -INF) bestRight.snd = pos;
L[0][pos] = bestLeft.snd;
distL[0][pos] = (pos - L[0][pos] + n) % n;
R[0][pos] = bestRight.snd;
distR[0][pos] = (R[0][pos] - pos + n) % n;
updateMaxi(pos, h[pos]);
}
forn(p, MAX_K - 1) forn(i, n) {
int j = L[p][i];
L[p + 1][i] = L[p][j];
distL[p + 1][i] = distL[p][i] + distL[p][j];
}
forn(p, MAX_K - 1) forn(i, n) {
int j = R[p][i];
R[p + 1][i] = R[p][j];
distR[p + 1][i] = distR[p][i] + distR[p][j];
}
}
bool reacheableLeft(int x, int y) {
ll currDist = (x - y + N) % N;
dforn(i, MAX_K) {
if (currDist >= distL[i][x]) {
currDist -= distL[i][x];
x = L[i][x];
}
}
return currDist < K && h[x] >= h[y];
}
bool reacheableRight(int x, int y) {
ll currDist = (y - x + N) % N;
dforn(i, MAX_K) {
if (currDist >= distR[i][x]) {
currDist -= distR[i][x];
x = R[i][x];
}
}
return currDist < K && h[x] >= h[y];
}
bool reacheable(int x, int y) {
return reacheableLeft(x, y) || reacheableRight(x, y);
}
int compare_plants(int x, int y) {
if (reacheable(x, y)) return 1;
if (reacheable(y, x)) return -1;
return 0;
}
