#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 n;
vector<int> st, lazy;
void build(int i, int l, int r, vector<int>& a){
if(l == r){
st[i] = a[l];
} else{
int m = (l + r) / 2;
build(2*i+1, l, m, a);
build(2*i+2, m+1, r, a);
st[i] = min(st[2*i+1], st[2*i+2]);
}
}
void build(int sz, vector<int>& a){
n = sz;
st.resize(4 * n, n+1);
lazy.resize(4 * n, 0);
build(0, 0, n - 1, a);
}
void push(int i){
if(lazy[i] != 0){
lazy[2*i+1] += lazy[i];
st[2*i+1] += lazy[i];
lazy[2*i+2] += lazy[i];
st[2*i+2] += lazy[i];
}
lazy[i] = 0;
}
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 res = -1;
if(res == -1){
res = ask(2*i+1, l, m, ql, qr);
}
if(res == -1){
res = ask(2*i+2, m + 1, r, ql, qr);
}
st[i] = min(st[2*i+1], st[2*i+2]);
return res;
}
int ask(int l, int r){
int res = ask(0, 0, n - 1, l, r);
return res;
}
void add(int i, int l, int r, int ql, int qr){
if(qr < l || ql > r){
return;
}
if(ql <= l && r <= qr){
st[i]--;
lazy[i]--;
return;
}
push(i);
int m = (l + r) / 2;
add(2*i+1, l, m, ql, qr);
add(2*i+2, m+1, r, ql, qr);
st[i] = min(st[2*i+1], st[2*i+2]);
}
void add(int l, int r){
add(0, 0, n - 1, l, r);
}
void pop(int i, int l, int r, int p, int k){
if(l == r){
st[i] = k;
return;
}
push(i);
int m = (l + r) / 2;
if(p <= m)
pop(2*i+1, l, m, p, k);
else
pop(2*i+2, m+1, r, p, k);
st[i] = min(st[2*i+1], st[2*i+2]);
}
void pop(int i, int k){
pop(0, 0, n-1, i, k);
}
};
int N, K;
vector<int> P, R;
SegmentTree st;
int ask(int l, int r){
return st.ask(l, r);
/*
for(int i = l; i <= r; i++){
if(R[i] == 0)
return i;
}
return -1;
*/
}
void pop(int i){
st.pop(i, N);
}
void add(int l, int r){
st.add(l, r);
/*
for(int i = l; i <= r; i++){
R[i]--;
}
*/
}
void f(int& n, int pos){
int pos2;
while(true){
pos2 = -1;
int l = pos - K + 1, r = pos - 1;
if(r < 0){
l += N, r += N;
pos2 = ask(l, r);
} else if(l < 0){
l += N;
pos2 = max(ask(0, r), ask(l, N-1));
} else{
pos2 = ask(l, r);
}
if(pos2 == -1){
break;
}
f(n, pos2);
}
P[pos] = n--;
pop(pos);
int l = pos - K + 1, r = pos - 1;
if(r < 0){
l += N, r += N;
add(l, r);
} else if(l < 0){
l += N;
add(0, r);
add(l, N-1);
} else{
add(l, r);
}
}
void genera(){
int n = N;
while(n >= 0){
int pos = ask(0, N-1);
f(n, pos);
}
}
vector<vector<int>> g, g2;
vector<bool> vis[2];
void bfs(int s){
vis[0].resize(N);
queue<int> q;
q.push(s);
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : g[v]){
if(vis[0][u] == false){
vis[0][u] = true;
q.push(u);
}
}
}
vis[1].resize(N);
q.push(s);
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : g2[v]){
if(vis[1][u] == false){
vis[1][u] = true;
q.push(u);
}
}
}
}
void init(int k, vector<int> r){
N = SZ(r), K = k, R = r;
P.resize(N);
st.build(N, r);
genera();
g.resize(N);
g2.resize(N);
for(int i = 0; i < N; i++){
for(int j = i + 1; j <= i + K - 1; j++){
if(P[i] > P[j % N]){
g[i].pb(j % N);
g2[j % N].pb(i);
} else{
g[j % N].pb(i);
g2[i].pb(j % N);
}
}
}
bfs(0);
}
int compare_plants(int x, int y){
if(x == 0){
if(vis[0][y])
return 1;
if(vis[1][y])
return -1;
return 0;
}
if(P[x] > P[y])
return 1;
if(P[x] < P[y])
return -1;
return 0;
}
