#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define len(v) (int) (v.size())
#define all(v) v.begin(), v.end()
struct SegmentTree {
int n;
vector<pair<int, int>> tree;
vector<int> push;
const pair<int, int> NEUTRAL = {1e9, -1};
void receive_update(int v, int upd) {
tree[v].first += upd;
push[v] += upd;
}
void do_push(int v) {
receive_update(2 * v, push[v]);
receive_update(2 * v + 1, push[v]);
push[v] = 0;
}
void build(int v, int l, int r, vector<int>& a) {
if (l + 1 == r) {
tree[v] = {a[l], l};
return;
}
int m = (l + r) / 2;
build(2 * v, l, m, a);
build(2 * v + 1, m, r, a);
tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
SegmentTree(vector<int>& a) {
n = len(a);
tree.resize(4 * n);
push.assign(4 * n, 0);
build(1, 0, n, a);
}
void modify(int v, int l, int r, int ql, int qr, int upd) {
if (r <= ql || qr <= l) return;
if (ql <= l && r <= qr) {
receive_update(v, upd);
return;
}
do_push(v);
int m = (l + r) / 2;
modify(2 * v, l, m, ql, qr, upd);
modify(2 * v + 1, m, r, ql, qr, upd);
tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
void modify(int ql, int qr, int upd) {
modify(1, 0, n, ql, qr, upd);
}
pair<int, int> get(int v, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) {
return NEUTRAL;
}
if (ql <= l && r <= qr) {
return tree[v];
}
do_push(v);
int m = (l + r) / 2;
return min(get(2 * v, l, m, ql, qr), get(2 * v + 1, m, r, ql, qr));
}
pair<int, int> get(int ql, int qr) {
return get(1, 0, n, ql, qr);
}
};
int n, k;
vector<int> r;
vector<int> val;
void init(int K, vector<int> R) {
r = R;
k = K;
n = len(r);
val.resize(n);
SegmentTree tree(r);
set<int> zero;
for (int cur = n - 1; cur >= 0; cur--) {
while (true) {
auto res = tree.get(0, n);
if (res.first == 0) {
zero.insert(res.second);
tree.modify(res.second, res.second + 1, 2 * n);
}
else {
break;
}
}
vector<int> idx(all(zero));
int mx = 0;
for (int i = 0; i < len(idx); i++) {
int dist;
if (i == 0) {
dist = idx[i] + n - idx.back();
}
else {
dist = idx[i] - idx[i - 1];
}
if (dist >= k) {
mx = idx[i];
break;
}
}
val[mx] = cur;
zero.erase(mx);
tree.modify(max(0, mx - k + 1), mx, -1);
tree.modify(min(n, n + mx - k + 1), n, -1);
}
// for (int i = 0; i < n; i++) {
// cout << val[i] << ' ';
// }
// cout << '\n';
}
int compare_plants(int x, int y) {
if (val[x] < val[y]) return -1;
return 1;
}
