#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
class LazySegTree {
struct Node {
int val = kInf;
int inc = 0;
};
const size_t n;
vector<Node> t;
static Node unite(const Node l, const Node r) {
Node ans{};
ans.val = min(l.val, r.val);
ans.inc = 0;
return ans;
}
void push(const int x, const int l, const int r) {
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
for (const int child : {x + 1, y}) {
t[child].val += t[x].inc;
t[child].inc += t[x].inc;
}
t[x].inc = 0;
}
void build(const int x, const int l, const int r, const vector<int> &a) {
if (l == r) {
t[x].val = a[l];
t[x].inc = 0;
return;
}
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
build(x + 1, l, mid, a);
build(y, mid + 1, r, a);
t[x] = unite(t[x + 1], t[y]);
}
int find_last_zero(const int x, const int l, const int r, const int ql, const int qr) {
if (l == r) {
return l;
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
int ans = -1;
if (ql <= mid and t[x + 1].val == 0) {
ans = max(ans, find_last_zero(x + 1, l, mid, ql, qr));
}
if (mid < qr and t[y].val == 0) {
ans = max(ans, find_last_zero(y, mid + 1, r, ql, qr));
}
return ans;
}
void update(const int x, const int l, const int r, const int ql, const int qr, const int value) {
if (ql <= l and r <= qr) {
t[x].val += value;
t[x].inc += value;
return;
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (ql <= mid) {
update(x + 1, l, mid, ql, qr, value);
}
if (mid < qr) {
update(y, mid + 1, r, ql, qr, value);
}
t[x] = unite(t[x + 1], t[y]);
}
Node query(const int x, const int l, const int r, const int ql, const int qr) {
if (ql <= l and r <= qr) {
return t[x];
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (qr <= mid) {
return query(x + 1, l, mid, ql, qr);
} else if (mid < ql) {
return query(y, mid + 1, r, ql, qr);
} else {
return unite(query(x + 1, l, mid, ql, qr),
query(y, mid + 1, r, ql, qr));
}
}
public:
explicit LazySegTree(const vector<int> &a) : n(a.size()), t(2 * n - 1) {
build(0, 0, (int) n - 1, a);
}
int find_last_zero(const int l, const int r) {
return find_last_zero(0, 0, (int) n - 1, l, r);
}
void update(const int l, const int r, const int x) {
update(0, 0, (int) n - 1, l, r, x);
}
int query(const int l, const int r) {
return query(0, 0, (int) n - 1, l, r).val;
}
};
vector<int> h;
void find_valid_arrangement(const int k, vector<int> &r) {
const int n = r.size();
r.insert(r.end(), r.begin(), r.end());
int tall = n - 1;
LazySegTree st(r);
auto point_update = [&](const int i) {
st.update(i, i, kInf);
st.update(i - n, i - n, kInf);
};
auto range_update = [&](int i) {
st.update(i - k + 1, i, -1);
i -= n;
const int j = i - k + 1;
st.update(max(0, j), i, -1);
if (j < 0) st.update(2 * n + j, 2 * n - 1, -1);
};
h.assign(n, -1);
function<void(int)> find_height = [&](const int i) {
while (st.query(i - k + 1, i - 1) == 0) {
const int j = st.find_last_zero(i - k + 1, i - 1);
find_height((j < n ? j + n : j));
}
h[i - n] = tall--;
point_update(i);
range_update(i);
};
while (tall >= 0) {
const int i = st.find_last_zero(n, 2 * n - 1);
find_height(i);
}
}
void init(int k, vector<int> r) {
find_valid_arrangement(k, r);
}
int compare_plants(int x, int y) {
if (h[x] > h[y]) return 1;
return -1;
}
