#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef tuple<int, int, int> iii;
typedef uint64_t u64;
typedef int64_t i64;
int k;
struct SegTree {
const iii id = { INT_MAX / 2, -1, 0 };
vector<iii> tree;
vi lazySub;
int n, N;
SegTree(vi v) {
n = v.size();
N = 1;
while (N < n)
N *= 2;
tree.resize(2 * N, id);
lazySub.resize(2 * N, 0);
loop(i, n)
tree[N + i] = { v[i], i, i };
for (int i = N - 1; i >= 1; i--)
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
iii merge(iii a, iii b) {
auto [v1, i1, r1] = a;
auto [v2, i2, r2] = b;
if (v1 < v2)
return a;
if (v2 < v1)
return b;
int v = v1, i, r = r2;
if (i2 - r1 >= k)
i = i2;
else
i = i1;
return { v, i, r };
}
void rangeSub(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
if (tl >= r || tr <= l)
return;
if (tl >= l && tr <= r)
{
get<0>(tree[i]) -= v;
lazySub[i] += v;
return;
}
if (i < N)
{
lazySub[2 * i] += lazySub[i];
lazySub[2 * i + 1] += lazySub[i];
get<0>(tree[2 * i]) -= lazySub[i];
get<0>(tree[2 * i + 1]) -= lazySub[i];
}
lazySub[i] = 0;
int tm = (tl + tr) / 2;
rangeSub(l, r, v, i * 2, tl, tm);
rangeSub(l, r, v, i * 2 + 1, tm, tr);
tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
}
iii range(int l, int r, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
if (tl >= r || tr <= l)
return id;
if (tl >= l && tr <= r)
return tree[i];
if (i < N)
{
lazySub[2 * i] += lazySub[i];
lazySub[2 * i + 1] += lazySub[i];
get<0>(tree[2 * i]) -= lazySub[i];
get<0>(tree[2 * i + 1]) -= lazySub[i];
}
lazySub[i] = 0;
int tm = (tl + tr) / 2;
return merge(range(l, r, i * 2, tl, tm), range(l, r, i * 2 + 1, tm, tr));
}
void set(int pos, int v, int i = 1, int tl = 0, int tr = -1)
{
if (tr == -1)
tr = N;
if (i >= N)
{
get<0>(tree[i]) = v;
return;
}
if (i < N)
{
lazySub[2 * i] += lazySub[i];
lazySub[2 * i + 1] += lazySub[i];
get<0>(tree[2 * i]) -= lazySub[i];
get<0>(tree[2 * i + 1]) -= lazySub[i];
}
lazySub[i] = 0;
int tm = (tl + tr) / 2;
if (pos < tm)
set(pos, v, i * 2, tl, tm);
else
set(pos, v, i * 2 + 1, tm, tr);
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
};
int n;
vi r;
vi perm;
void init(int _k, vi _r)
{
n = _r.size();
k = _k;
r = _r;
perm.assign(n, 0);
SegTree segTree(r);
int idx = n - 1;
vb vis(n);
/*cout << "R: ";
for (int x : r)
cout << x << ' ';
cout << endl;
cout << "Low: ";*/
while (idx >= 0)
{
/*vi lowest;
int count = 0;
for (int i = 1; i < k; i++)
count += vis[i];
loop(i, n)
{
if (r[i] == count && !vis[i])
lowest.push_back(i);
count -= vis[(i + 1) % n];
count += vis[(i + k) % n];
}*/
/*int n2 = lowest.size();
int low = lowest[0];
loop(i, n2 - 1)
{
if (lowest[i + 1] - lowest[i] >= k)
{
low = lowest[i + 1];
break;
}
}*/
auto [lowVal, low, maxR] = segTree.range(0, n);
//cout << low << ' ';
if (low - k + 1 < 0)
{
segTree.rangeSub(0, low, 1);
segTree.rangeSub(n + low - k + 1, n, 1);
}
else
{
segTree.rangeSub(low - k + 1, low, 1);
}
segTree.set(low, INT_MAX / 2);
vis[low] = true;
perm[low] = idx--;
}
/*cout << endl;
cout << "Perm: ";
for (int x : perm)
cout << x << ' ';
cout << endl;*/
}
int compare_plants(int x, int y)
{
if (perm[x] < perm[y])
return -1;
if (perm[x] > perm[y])
return 1;
return 0;
}
