// In the name of Allah
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node {
ll lazy; pll min;
};
const int maxn = 2e5 + 7;
const int maxlg = 20;
const ll oo = 1e9 + 7;
int n, k;
int A[maxn], val[maxn];
set<int> st, stx; node t[4 * maxn];
int val1[maxn][maxlg], val2[maxn][maxlg];
pll up1[maxn][maxlg], up2[maxn][maxlg];
set<pii> stw; int arr[maxn];
bool cmp(int i, int j) {
return (val[i] > val[j]);
}
void build(int v, int tl, int tr) {
t[v].lazy = 0;
if (tr - tl == 1) {
t[v].min = Mp(A[tl], tl);
return ;
}
int mid = (tl + tr) / 2;
build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
t[v].min = min(t[2 * v + 1].min, t[2 * v + 2].min); t[v].min.F += t[v].lazy;
}
void add_val(int v, int tl, int tr, int l, int r, ll x) {
l = max(l, tl); r = min(r, tr);
if (l >= tr || r <= tl) return ;
if (l == tl && r == tr) {
t[v].min.F += x; t[v].lazy += x;
return ;
}
int mid = (tl + tr) / 2;
add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
t[v].min = min(t[2 * v + 1].min, t[2 * v + 2].min); t[v].min.F += t[v].lazy;
}
void checkx(int j) {
stx.erase(j); int d = 0;
auto it = st.lower_bound(j);
if (it != st.begin()) {
it--; d = (j - *it);
}
else d = (j - *st.rbegin() + n);
if (d >= k) stx.insert(j);
}
void addx(int j) {
st.insert(j); checkx(j);
if (len(st) == 1) return ;
auto it = st.upper_bound(j);
if (it != st.end()) checkx(*it);
else checkx(*st.begin());
}
bool ok1(int v, int x, int d) {
ll res = 0;
for (int j = maxlg - 1; j >= 0; j--) {
if (val1[v][j] <= x) {
res += up1[v][j].F;
v = up1[v][j].S;
if (res >= d) return 1;
}
}
return (res >= d);
}
int ok2(int v, int x, int d) {
ll res = 0;
for (int j = maxlg - 1; j >= 0; j--) {
if (val2[v][j] <= x) {
res += up2[v][j].F;
v = up2[v][j].S;
if (res >= d) return 1;
}
}
return (res >= d);
}
void delx(int j) {
st.erase(j); stx.erase(j);
if (len(st) == 0) return ;
auto it = st.upper_bound(j);
if (it != st.end()) checkx(*it);
else checkx(*st.begin());
}
void init(int Kx, vector<int> Ax) {
n = len(Ax); k = Kx;
for (int i = 0; i < n; i++) A[i] = Ax[i];
build(0, 0, n);
int sz = 0;
while (sz < n) {
while (t[0].min.F == 0) {
int j = t[0].min.S;
add_val(0, 0, n, j, j + 1, oo);
addx(j);
}
int j = *stx.begin(); val[j] = sz++;
int x1 = min(j, k - 1), x2 = (k - 1) - x1;
add_val(0, 0, n, j - x1, j, -1);
add_val(0, 0, n, n - x2, n, -1);
delx(j);
}
stw.clear();
for (int j = 0; j < k; j++) stw.insert(Mp(val[j], j));
for (int i = 0; i < n; i++) {
int j = (i + k - 1) % n, r = -1;
auto it = stw.upper_bound(Mp(val[i], oo));
if (it != stw.end()) r = (*it).S;
else r = i;
up1[i][0] = Mp((r - i + n) % n, r);
val1[i][0] = val[r];
it = stw.upper_bound(Mp(val[j], oo));
if (it != stw.end()) r = (*it).S;
else r = j;
up2[j][0] = Mp((j - r + n) % n, r);
val2[j][0] = val[r];
stw.erase(Mp(val[i], i));
r = (i + k) % n;
stw.insert(Mp(val[r], r));
}
iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
for (int i = 0; i < n; i++) {
int v = arr[i];
for (int j = 1; j < maxlg; j++) {
int u = up1[v][j - 1].S;
up1[v][j] = Mp(up1[v][j - 1].F + up1[u][j - 1].F, up1[u][j - 1].S);
val1[v][j] = val1[u][j - 1];
u = up2[v][j - 1].S;
up2[v][j] = Mp(up2[v][j - 1].F + up2[u][j - 1].F, up2[u][j - 1].S);
val2[v][j] = val2[u][j - 1];
}
}
return ;
}
int compare_plants(int x, int y) {
if (val[x] < val[y]) {
int d1 = (y - x + n) % n;
int d2 = (x - y + n) % n;
if (!ok1(x, val[y], d1) && !ok2(x, val[y], d2)) return 0;
}
else {
int d1 = (x - y + n) % n;
int d2 = (y - x + n) % n;
if (!ok1(y, val[x], d1) && !ok2(y, val[x], d2)) return 0;
}
if (val[x] < val[y]) return 1;
else return -1;
}
