#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
class SegmentTree{
public:
int sz;
vector<int> st, lazy;
void push(int i){
if(lazy[i]){
st[2 * i + 1] += lazy[i];
lazy[2 * i + 1] += lazy[i];
st[2 * i + 2] += lazy[i];
lazy[2 * i + 2] += lazy[i];
}
lazy[i] = 0;
}
void merge(int i){
st[i] = min(st[2 * i + 1], st[2 * i + 2]);
}
void build(int i, int l, int r, vector<int>& R){
if(l == r){
st[i] = R[l];
} else{
int m = (l + r) / 2;
build(2*i+1, l, m, R);
build(2*i+2, m+1, r, R);
merge(i);
}
}
void build(int n, vector<int>& R){
sz = n;
st.resize(4 * sz);
lazy.resize(4 * sz);
build(0, 0, n - 1, R);
}
int ask(int i, int l, int r, int ql, int qr){
if(qr < l || ql > r || st[i] != 0){
return -1;
}
if(l == r){
return l;
}
push(i);
int m = (l + r) / 2;
int ans = ask(2 * i + 1, l, m, ql, qr);
if(ans == -1)
ans = ask(2 * i + 2, m + 1, r, ql, qr);
return ans;
}
void add(int i, int l, int r, int ql, int qr, int k){
if(ql <= l && r <= qr){
st[i] += k;
lazy[i] += k;
return;
}
if(qr < l || ql > r){
return;
}
push(i);
int m = (l + r) / 2;
add(2 * i + 1, l, m, ql, qr, k);
add(2 * i + 2, m + 1, r, ql, qr, k);
merge(i);
}
};
SegmentTree st;
int N, K;
vector<int> R, P;
int ask(int l, int r){
return st.ask(0, 0, N - 1, l, r);
}
void add(int l, int r, int k){
st.add(0, 0, N - 1, l, r, k);
}
void f(int& n, int i){
int j = -1;
while(1){
int l = i - K + 1, r = i - 1;
if(r < 0){
l += N, r += N;
j = ask(l, r);
} else if(l < 0){
l += N;
j = max(ask(0, r), ask(l, N-1));
} else{
j = ask(l, r);
}
if(j == -1) break;
f(n, j);
}
P[i] = n--;
add(i, i, N+1);
int l = i - K + 1, r = i - 1;
if(r < 0){
l += N, r += N;
add(l, r, -1);
} else if(l < 0){
add(0, r, -1);
l += N;
add(l, N-1, -1);
} else{
add(l, r, -1);
}
}
void build_plants(){
st.build(N, R);
int n = N;
while(n){
f(n, ask(0, N-1));
}
}
void init(int k, vector<int> r){
N = SZ(r), K = k, R = r;
P.resize(N);
build_plants();
}
int compare_plants(int x, int y){
if(P[x] > P[y]){
return 1;
} else if(P[x] < P[y]){
return -1;
} else{
return 0;
}
}
