#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 uint64_t u64;
typedef int64_t i64;
int k;
struct SegTree {
const ii id = { INT_MAX, 0 };
vii 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 };
for (int i = N - 1; i >= 1; i--)
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
ii merge(ii a, ii b) {
if (a.first < b.first)
return a;
if (b.first < a.first || b.second - a.second >= k)
return b;
return a;
}
void rangeSub(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
if (tl >= l && tr <= r)
lazySub[i] = v;
if (tl >= r || tr <= l)
return;
int tm = (tl + tr) / 2;
range(l, r, i * 2, tl, tm);
range(l, r, i * 2 + 1, tm, tr);
}
ii range(int l, int r, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
tree[i].first -= lazySub[i];
if (tr - tl > 1)
{
lazySub[2 * i] = lazySub[i];
lazySub[2 * i + 1] = lazySub[i];
}
lazySub[i] = 0;
if (tl >= l && tr <= r)
return tree[i];
if (tl >= r || tr <= l)
return id;
int tm = (tl + tr) / 2;
return merge(range(l, r, i * 2, tl, tm), range(l, r, i * 2 + 1, tm, tr));
}
};
int n;
vi r;
vi perm;
void init(int _k, vi _r)
{
n = _r.size();
k = _k;
r = _r;
perm.assign(n, 0);
int idx = n;
vb vis(n);
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;
}
}
vis[low] = true;
perm[low] = idx--;
}
}
int compare_plants(int x, int y)
{
if (perm[x] < perm[y])
return -1;
if (perm[x] > perm[y])
return 1;
return 0;
}
