#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));
}
}
class MergeSortTree{
public:
int sz;
vector<vector<pii>> st;
void combine(int i){
for(auto x : st[2 * i + 1]){
st[i].pb(x);
}
for(auto x : st[2 * i + 2]){
st[i].pb(x);
}
sort(all(st[i]));
}
void build(int i, int l, int r, vector<int>& P){
if(l == r){
st[i].pb({P[l], l});
} else{
int m = (l + r) / 2;
build(2 * i + 1, l, m, P);
build(2 * i + 2, m + 1, r, P);
combine(i);
}
}
void build(int n, vector<int>& P){
sz = n;
st.resize(4 * n);
build(0, 0, n - 1, P);
}
pii best(pii a, pii b){
if(a.ff > b.ff) return a;
return b;
}
pii query(int i, int l, int r, int ql, int qr, int k){
if(ql <= l && r <= qr){
pii p = {k, -1};
int pos = upper_bound(all(st[i]), p) - st[i].begin() - 1;
if(pos < 0){
return {-1, -1};
}
return st[i][pos];
}
if(qr < l || ql > r){
return {-1, -1};
}
int m = (l + r) / 2;
pii a = query(2 * i + 1, l, m, ql, qr, k);
pii b = query(2 * i + 2, m + 1, r, ql, qr, k);
return best(a, b);
}
pii query(int l, int r, int k){
return query(0, 0, sz - 1, l, r, k);
}
};
MergeSortTree mt;
pii best(pii a, pii b){
if(a.ff > b.ff) return a;
return b;
}
pii query(int l, int r, int k){
return mt.query(l, r, k);
}
vector<vector<int>> g;
void build_graph(){
g.resize(N);
mt.build(N, P);
for(int i = 0; i < N; i++){
int l, r;
pii u;
l = i + 1, r = i + K - 1;
if(l >= N){
l %= N, r %= N;
u = query(l, r, P[i]);
} else if(r >= N){
r %= N;
u = best(query(l, N - 1, P[i]), query(0, r, P[i]));
} else{
u = query(l, r, P[i]);
}
if(u.ss != -1){
g[i].pb(u.ss);
}
l = i - K + 1, r = i - 1;
if(r < 0){
l += N, r += N;
u = query(l, r, P[i]);
} else if(l < 0){
l += N;
u = best(query(0, r, P[i]), query(l, N - 1, P[i]));
} else{
u = query(l, r, P[i]);
}
if(u.ss != -1){
g[i].pb(u.ss);
}
}
}
vector<vector<bool>> vis;
void bfs(int s){
vis[s].resize(N, false);
queue<int> q;
q.push(s);
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : g[v]){
if(!vis[s][u]){
vis[s][u] = true;
q.push(u);
}
}
}
}
void init(int k, vector<int> r) {
N = SZ(r), K = k, R = r;
P.resize(N);
build_plants();
build_graph();
if(N <= 300){
vis.resize(N);
for(int i = 0; i < N; i++){
bfs(i);
}
} else{
vis.resize(1);
bfs(0);
}
}
int compare_plants(int x, int y) {
if(N <= 300 || x == 0){
if(vis[x][y]){
return 1;
} else if(vis[y][x]){
return -1;
} else{
return 0;
}
}
if(P[x] > P[y]){
return 1;
} else if(P[x] < P[y]){
return -1;
} else{
return 0;
}
}
