#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
int seg[1 << 19];
int lb[1 << 19];
int rb[1 << 19];
int lazy[1 << 19];
int sidx[1 << 19];
void build(int c, int l, int r) {
lb[c] = l;
rb[c] = r;
sidx[c] = l;
if (l == r)
return;
int k = (l + r) / 2;
build(2 * c, l, k);
build(2 * c + 1, k + 1, r);
}
void prop(int c) {
if (lazy[c]) {
seg[c] += lazy[c];
if (lb[c] != rb[c]) {
lazy[2 * c] += lazy[c];
lazy[2 * c + 1] += lazy[c];
}
lazy[c] = 0;
}
}
void update(int c, int l, int r, int x) {
if (lb[c] == l && rb[c] == r)
lazy[c] += x;
prop(c);
if (lb[c] == l && rb[c] == r)
return;
int k = (lb[c] + rb[c]) / 2;
if (l <= k && k < r) {
update(2 * c, l, k, x);
update(2 * c + 1, k + 1, r, x);
} else if (r <= k) {
update(2 * c, l, r, x);
prop(2 * c + 1);
} else {
prop(2 * c);
update(2 * c + 1, l, r, x);
}
if (seg[2 * c] <= seg[2 * c + 1]) {
seg[c] = seg[2 * c];
sidx[c] = sidx[2 * c];
} else {
seg[c] = seg[2 * c + 1];
sidx[c] = sidx[2 * c + 1];
}
}
pair<int, int> query(int c, int l, int r) {
prop(c);
if (lb[c] == l && rb[c] == r)
return make_pair(seg[c], sidx[c]);
int k = (lb[c] + rb[c]) / 2;
if (l <= k && k < r)
return min(query(2 * c, l, k), query(2 * c + 1, k + 1, r));
else if (r <= k)
return query(2 * c, l, r);
else
return query(2 * c + 1, l, r);
}
vector<int> h; // recovered
void init(int k, vector<int> r) {
int n = r.size();
h.resize(n, 0);
build(1, 0, n - 1);
for (int i = 0; i < n; i++) {
update(1, i, i, r[i]);
}
for (int it = 0; it < n; it++) {
int m = query(1, 0, n - 1).second;
if (m + k < n) {
auto p = query(1, m + k, n - 1);
if (p.first == 0) {
m = p.second;
}
}
// printf("DBG %d\n", m);
h[m] = n - it;
if (m >= k - 1) {
update(1, m - k + 1, m - 1, -1);
} else {
if (m != 0)
update(1, 0, m - 1, -1);
update(1, m + n - k + 1, n - 1, -1);
}
update(1, m, m, 1e9);
}
}
int compare_plants(int x, int y) { return h[x] > h[y] ? 1 : -1; }
