#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
int segmin[1 << 19];
int segmax[1 << 19];
int lb[1 << 19];
int rb[1 << 19];
int lazymin[1 << 19];
int lazymax[1 << 19];
int sminidx[1 << 19];
int smaxidx[1 << 19];
void build(int c, int l, int r) {
lb[c] = l;
rb[c] = r;
sminidx[c] = l;
smaxidx[c] = l;
if (l == r)
return;
int k = (l + r) / 2;
build(2 * c, l, k);
build(2 * c + 1, k + 1, r);
}
void propmin(int c) {
if (lazymin[c]) {
segmin[c] += lazymin[c];
if (lb[c] != rb[c]) {
lazymin[2 * c] += lazymin[c];
lazymin[2 * c + 1] += lazymin[c];
}
lazymin[c] = 0;
}
}
void propmax(int c) {
if (lazymax[c]) {
segmax[c] += lazymax[c];
if (lb[c] != rb[c]) {
lazymax[2 * c] += lazymax[c];
lazymax[2 * c + 1] += lazymax[c];
}
lazymax[c] = 0;
}
}
void updatemin(int c, int l, int r, int x) {
if (lb[c] == l && rb[c] == r)
lazymin[c] += x;
propmin(c);
if (lb[c] == l && rb[c] == r)
return;
int k = (lb[c] + rb[c]) / 2;
if (l <= k && k < r) {
updatemin(2 * c, l, k, x);
updatemin(2 * c + 1, k + 1, r, x);
} else if (r <= k) {
updatemin(2 * c, l, r, x);
propmin(2 * c + 1);
} else {
propmin(2 * c);
updatemin(2 * c + 1, l, r, x);
}
if (segmin[2 * c] <= segmin[2 * c + 1]) {
segmin[c] = segmin[2 * c];
sminidx[c] = sminidx[2 * c];
} else {
segmin[c] = segmin[2 * c + 1];
sminidx[c] = sminidx[2 * c + 1];
}
}
void updatemax(int c, int l, int r, int x) {
if (lb[c] == l && rb[c] == r)
lazymax[c] += x;
propmax(c);
if (lb[c] == l && rb[c] == r)
return;
int k = (lb[c] + rb[c]) / 2;
if (l <= k && k < r) {
updatemax(2 * c, l, k, x);
updatemax(2 * c + 1, k + 1, r, x);
} else if (r <= k) {
updatemax(2 * c, l, r, x);
propmax(2 * c + 1);
} else {
propmax(2 * c);
updatemax(2 * c + 1, l, r, x);
}
if (segmax[2 * c] >= segmax[2 * c + 1]) {
segmax[c] = segmax[2 * c];
smaxidx[c] = smaxidx[2 * c];
} else {
segmax[c] = segmax[2 * c + 1];
smaxidx[c] = smaxidx[2 * c + 1];
}
}
pair<int, int> querymin(int c, int l, int r) {
propmin(c);
if (lb[c] == l && rb[c] == r)
return make_pair(segmin[c], sminidx[c]);
int k = (lb[c] + rb[c]) / 2;
if (l <= k && k < r)
return min(querymin(2 * c, l, k), querymin(2 * c + 1, k + 1, r));
else if (r <= k)
return querymin(2 * c, l, r);
else
return querymin(2 * c + 1, l, r);
}
pair<int, int> querymax(int c, int l, int r) {
propmax(c);
if (lb[c] == l && rb[c] == r)
return make_pair(segmax[c], smaxidx[c]);
int k = (lb[c] + rb[c]) / 2;
if (l <= k && k < r)
return max(querymax(2 * c, l, k), querymax(2 * c + 1, k + 1, r),
[](pair<int, int> x, pair<int, int> y) {
return x.first < y.first ? true
: x.first > y.first ? false
: x.second > y.second;
});
else if (r <= k)
return querymax(2 * c, l, r);
else
return querymax(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++) {
updatemin(1, i, i, r[i]);
updatemax(1, i, i, r[i]);
}
int topptr = 0;
int botptr = 0;
for (int it = 0; it < n; it++) {
int m = querymin(1, 0, n - 1).second;
bool minfail = false;
if (m + k < n) {
auto p = querymin(1, m + k, n - 1);
if (p.first == 0) {
m = p.second;
}
if (m + k >= n) {
p = querymin(1, m + k - n, m - 1);
if (p.first == 0) {
minfail = true;
}
} else {
minfail = true;
}
}
if (!minfail) {
// printf("DBG %d\n", m);
h[m] = n - topptr++;
if (m >= k - 1) {
updatemin(1, m - k + 1, m - 1, -1);
} else {
if (m != 0) {
updatemin(1, 0, m - 1, -1);
}
updatemin(1, m + n - k + 1, n - 1, -1);
}
updatemin(1, m, m, 1e9);
updatemax(1, m, m, -1e9);
} else {
m = querymax(1, 0, n - 1).second;
if (m + k < n) {
auto p = querymax(1, m + k, n - 1);
if (p.first == k - 1) {
m = p.second;
}
}
h[m] = ++botptr;
if (m >= k - 1) {
updatemax(1, m - k + 1, m - 1, 1);
} else {
if (m != 0) {
updatemax(1, 0, m - 1, 1);
}
updatemax(1, m + n - k + 1, n - 1, 1);
}
updatemin(1, m, m, 1e9);
updatemax(1, m, m, -1e9);
}
}
}
int compare_plants(int x, int y) { return h[x] > h[y] ? 1 : -1; }
