#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
int curVal;
vector<int> p;
struct SegmentTree{
int n;
vector<int> d, lazy;
void build(int id, int l, int r, const vector<int> &a){
if (l == r){
d[id] = a[l];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid, a);
build(id << 1 | 1, mid + 1, r, a);
d[id] = min(d[id << 1], d[id << 1 | 1]);
}
void init(const vector<int> &a){
n = a.size();
d.assign(n * 4 + 1, 0);
lazy.assign(n * 4 + 1, 0);
build(1, 0, n - 1, a);
}
void doLazy(int id, int l, int r){
d[id] += lazy[id];
if (l < r){
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
}
lazy[id] = 0;
return;
}
void update(int id, int l, int r, int u, int v, int val){
doLazy(id, l, r);
if (v < l || r < u)
return;
if (u <= l && r <= v){
lazy[id] += val;
doLazy(id, l, r);
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
d[id] = min(d[id << 1], d[id << 1 | 1]);
}
void update(int l, int r, int val){
if (l <= r){
update(1, 0, n - 1, l, r, val);
} else {
update(1, 0, n - 1, l, n - 1, val);
update(1, 0, n - 1, 0, r, val);
}
}
int findPos0(int id, int l, int r, int u, int v){
doLazy(id, l, r);
if (v < l || r < u || d[id] > 0)
return -1;
if (l == r)
return l;
int mid = (l + r) >> 1;
int res = findPos0(id << 1, l, mid, u, v);
if (res == -1)
res = findPos0(id << 1 | 1, mid + 1, r, u, v);
return res;
}
int findPos0(int l, int r){
if (l <= r)
return findPos0(1, 0, n - 1, l, r);
int res = findPos0(1, 0, n - 1, l, n - 1);
if (res == -1)
res = findPos0(1, 0, n - 1, 0, r);
return res;
}
} st;
void process(int pos, int n, int k){
while (true){
int nxt = st.findPos0((pos - k + 1 + n) % n, (pos - 1 + n) % n);
if (nxt == -1)
break;
else
process(nxt, n, k);
}
p[pos] = curVal--;
st.update(pos, pos, 1e9);
st.update((pos - k + 1 + n) % n, (pos - 1 + n) % n, -1);
}
void init(int k, vector<int> r) {
int n = r.size();
p.assign(n, -1);
st.init(r);
curVal = n - 1;
while (curVal >= 0){
int pos = st.findPos0(0, n - 1);
assert(pos != -1);
process(pos, n, k);
}
return;
}
int compare_plants(int x, int y) {
if (p[x] > p[y])
return 1;
else
return -1;
return 0;
}
