#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, K;
vector<int> R, A, pfs;
void init(int k, std::vector<int> r) {
K = k, R = r; N = R.size();
A.resize(N, -1);
if (K == 2) {
pfs.resize(N + 1);
for (int i = 0; i < N; i++) {
pfs[i + 1] = pfs[i] + R[i];
}
return;
}
int M = 2 << __lg(N - 1);
vector<int> st(2 * M - 1), lazy(2 * M - 1);
auto push = [&](int p) {
st[p * 2 + 1] += lazy[p];
st[p * 2 + 2] += lazy[p];
lazy[p * 2 + 1] += lazy[p];
lazy[p * 2 + 2] += lazy[p];
lazy[p] = 0;
};
auto pull = [&](int p) {
st[p] = max(st[p * 2 + 1], st[p * 2 + 2]);
};
for (int i = 0; i < N; i++) {
st[i + M - 1] = R[i];
}
for (int i = M - 2; i >= 0; i--) {
pull(i);
}
auto modify = [&](auto f, int p, int l, int r, int x, int v) -> void {
if (r - l == 1) {
st[p] = v;
return;
}
int m = (l + r + 1) / 2;
push(p);
if (x < m) {
f(f, p * 2 + 1, l, m, x, v);
} else {
f(f, p * 2 + 2, m, r, x, v);
}
pull(p);
};
auto update = [&](auto f, int p, int l, int r, int L, int R) -> void {
if (R <= l || r <= L) {
return;
}
if (L <= l && r <= R) {
st[p]++;
lazy[p]++;
return;
}
int m = (l + r + 1) / 2;
push(p);
f(f, p * 2 + 1, l, m, L, R);
f(f, p * 2 + 2, m, r, L, R);
pull(p);
};
auto find = [&](auto f, int p, int l, int r) {
if (r - l == 1) {
return l;
}
int m = (l + r + 1) / 2;
push(p);
if (st[p * 2 + 1] == K - 1) {
return f(f, p * 2 + 1, l, m);
} else {
return f(f, p * 2 + 2, m, r);
}
};
for (int i = 0; i < N; i++) {
vector<int> v;
while (st[0] == K - 1) {
int x = find(find, 0, 0, M);
v.push_back(x);
modify(modify, 0, 0, M, x, -1e9);
}
int m = v.size(), p;
if (m == 1 || N - v[m - 1] + v[0] >= K) {
p = v[0];
} else {
for (int j = 0; j + 1 < m; j++) {
if (v[j + 1] - v[j] >= K) {
p = v[j + 1];
}
}
}
A[p] = i;
R[p] = -1e9;
for (int x : v) {
if (x != p) {
modify(modify, 0, 0, M, x, K - 1);
}
}
if (p > 0) {
update(update, 0, 0, M, max(0, p - (K - 1)), p);
}
if (p - (K - 1) < 0) {
update(update, 0, 0, M, N + p - (K - 1), N);
}
}
}
int compare_plants(int x, int y) {
if (K == 2) {
if (pfs[y] - pfs[x] == 0) {
return 1;
}
if (pfs[y] - pfs[x] == y - x) {
return -1;
}
if (pfs[N] - pfs[y] + pfs[x] == 0) {
return -1;
}
if (pfs[N] - pfs[y] + pfs[x] == N - y + x) {
return 1;
}
}
return A[x] > A[y] ? 1 : -1;
}
