#include "plants.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 200'000;
int n, k;
int dist(int s, int t) {
if(s <= t) return t - s;
else return t - s + n;
}
struct Ayaya {
set<int> pos;
set<pii> d;
pii find(int x) {
auto itr = pos.upper_bound(x);
if(itr == pos.end()) {
itr = pos.begin();
}
auto itl = pos.lower_bound(x);
if(itl == pos.begin()) {
itl = prev(pos.end());
} else {
itl = prev(itl);
}
return pii(*itl, *itr);
}
void insert(int x) {
if(sz(pos) == 0) {
pos.insert(x);
d.emplace(0, x);
return;
}
int l, r; tie(l, r) = find(x);
d.erase(pii(dist(l, r), r));
d.insert(pii(dist(l, x), x));
d.insert(pii(dist(x, r), r));
pos.insert(x);
}
void erase(int x) {
if(sz(pos) == 1) {
pos.clear(); d.clear();
return;
}
int l, r; tie(l, r) = find(x);
d.erase(pii(dist(l, x), x));
d.erase(pii(dist(x, r), r));
d.insert(pii(dist(l, r), r));
pos.erase(x);
}
int pop() {
int i = prev(d.end())->S;
erase(i);
return i;
}
void out() {
for(auto &i:pos) cerr << i << " ";
cerr << "\n";
for(auto &i:d) cerr << "(" << i.F << ", " << i.S << ") ";
cerr << "\n";
}
} aya;
#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
int add[MAXN * 4 + 10];
pii mn[MAXN * 4 + 10]; // {value, index}
void pull(int id) {
mn[id] = min(mn[L(id)], mn[R(id)]);
mn[id].F += add[id];
}
void build(int id, int l, int r, int *owo) {
add[id] = 0;
if(l == r) {
add[id] = owo[l];
mn[id] = pii(owo[l], l);
return;
}
int m = (l + r) / 2;
build(L(id), l, m, owo);
build(R(id), m + 1, r, owo);
pull(id);
}
void range_add(int id, int l, int r, int L, int R, int val) {
if(L > R) {
range_add(0, 0, n - 1, L, n - 1, val);
range_add(0, 0, n - 1, 0, R, val);
return;
}
if(l >= L && r <= R) {
add[id] += val; mn[id].F += val;
return;
}
int m = (l + r) / 2;
if(L <= m) range_add(L(id), l, m, L, R, val);
if(R > m) range_add(R(id), m + 1, r, L, R, val);
pull(id);
}
pii find_min(int id, int l, int r, int L, int R) {
if(L > R) {
return min(
find_min(0, 0, n - 1, L, n - 1),
find_min(0, 0, n - 1, 0, R)
);
}
if(l >= L && r <= R) return mn[id];
int m = (l + r) / 2;
pii res(n * 8, -1);
if(L <= m) res = min(res, find_min(L(id), l, m, L, R));
if(R > m) res = min(res, find_min(R(id), m + 1, r, L, R));
res.F += add[id];
return res;
}
void kill_all() {
pii res = find_min(0, 0, n - 1, 0, n - 1);
while(res.F == 0) {
aya.insert(res.S);
range_add(0, 0, n - 1, res.S, res.S, n * 888);
res = find_min(0, 0, n - 1, 0, n - 1);
}
}
} seg;
int r[MAXN + 10];
int rk[MAXN + 10];
int pos[MAXN + 10];
int pl[MAXN + 10];
int pr[MAXN + 10];
int sl[MAXN + 10];
int sr[MAXN + 10];
void init(int __k, vector<int> __r) {
k = __k;
n = sz(__r);
For(i, 0, n - 1) r[i] = __r[i];
seg.build(0, 0, n - 1, r);
seg.kill_all();
For(rank, 1, n) {
int idx = aya.pop();
seg.range_add(0, 0, n - 1, (idx + n - k + 1) % n, (idx + n - 1) % n, -1);
seg.kill_all();
rk[idx] = rank;
pos[rank] = idx;
}
seg.build(0, 0, n - 1, rk);
For(rank, 1, n) {
int idx = pos[rank];
pii owo;
owo = seg.find_min(0, 0, n - 1, (idx + n - k + 1) % n, (idx + n - 1) % n);
pl[idx] = (owo.F <= n ? owo.S : idx);
owo = seg.find_min(0, 0, n - 1, (idx + 1) % n, (idx + k - 1) % n);
pr[idx] = (owo.F <= n ? owo.S : idx);
sl[idx] = dist(pl[idx], idx);
sr[idx] = dist(idx, pr[idx]);
seg.range_add(0, 0, n - 1, idx, idx, n * 888);
}
// For(i, 0, n - 1) cerr << rk[i] << " \n"[i == n - 1];
// For(i, 0, n - 1) cerr << pl[i] << " \n"[i == n - 1];
// For(i, 0, n - 1) cerr << sl[i] << " \n"[i == n - 1];
// For(i, 0, n - 1) cerr << pr[i] << " \n"[i == n - 1];
// For(i, 0, n - 1) cerr << sr[i] << " \n"[i == n - 1];
For(_, 1, 49) {
For(rank, 1, n) {
int idx = pos[rank];
sl[idx] += sl[pl[idx]];
pl[idx] = pl[pl[idx]];
sr[idx] += sr[pr[idx]];
pr[idx] = pr[pr[idx]];
}
// For(i, 0, n - 1) cerr << sr[i] << " \n"[i == n - 1];
}
}
int compare_plants(int x, int y) {
if(rk[x] > rk[y]) return -compare_plants(y, x);
bool uwu = false;
if(sl[x] >= n - 1) uwu = true;
if(sl[x] >= dist(y, x)) uwu = true;
if(sr[x] >= dist(x, y)) uwu = true;
return (uwu ? (rk[x] < rk[y] ? 1 : -1) : 0);
}
