#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define lc (rt<<1)
#define rc (rt<<1|1)
#define pb push_back
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vii;
typedef vector<pii> viii;
const int inf = 0x3F3F3F3F;
const ll infl = 0x3F3F3F3F3F3F3F3FLL;
const int mod = 1e9 + 7, MM = 2e5+5;
int N, K, lz[6*MM], mi[6*MM], stk[MM], tp=-1; vi ord1, ord2;
void pushdn(int rt){
mi[lc]+=lz[rt]; mi[rc]+=lz[rt];
lz[lc]+=lz[rt]; lz[rc]+=lz[rt]; lz[rt]=0;
}
void upd(int L, int R, int l, int r, int val, int rt){
if(r < L || l > R) return;
if(l <= L && R <= r){ mi[rt]+=val; lz[rt]+=val; return; }
if(lz[rt]) pushdn(rt);
int mid = (L+R)/2;
if(l <= mid) upd(L, mid, l, r, val, lc);
if(r > mid) upd(mid+1, R, l, r, val, rc);
mi[rt] = min(mi[lc], mi[rc]);
}
int qry(int L, int R, int rt){
if(mi[rt] > 0) return -1;
if(L==R) return L;
if(lz[rt]) pushdn(rt);
int mid = (L+R)/2;
if(mi[lc] > 0) return qry(mid+1, R, rc);
return qry(L, mid, lc);
}
vi solve(vi& r){
vi ret(N); cl(lz, 0); cl(mi, 0);
for(int i=0; i<N; i++)
upd(0, N-1, i, i, r[i], 1);
for(int i=0; i<N; i++){
int pos = qry(0, N-1, 1);
while(pos < 0 && tp >= 0){
upd(0, N-1, stk[tp--], N-1, -1, 1);
pos = qry(0, N-1, 1);
}
ret[pos] = i;
upd(0, N-1, pos, pos, inf, 1);
upd(0, N-1, pos-K+1, pos-1, -1, 1);
if(pos-K+1<0) stk[++tp] = pos+N-K;
}
// for(int x: ret) cout << x << " ";
// cout << endl;
return ret;
}
void init(int k, vi r){
r.insert(r.end(), r.begin(), r.end());
N = r.size(); K = k;
ord1 = solve(r);
for(int &x: r) x = k-1-x;
ord2 = solve(r);
}
int compare_plants(int x, int y){
if(x > y) return -compare_plants(y, x);
if(ord1[x] > ord1[y] || ord2[x+N/2] < ord2[y]) return -1;
if(ord2[x] > ord2[y] || ord1[x+N/2] < ord1[y]) return 1;
return 0;
}
//int main(){
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// int k=3; vi a={0, 1, 1, 2};
// init(k, a);
// for(int i=0; i<a.size(); i++)
// for(int j=i+1; j<a.size(); j++)
// cout << i << " vs " << j << " = " << compare_plants(i, j) << endl;
//}
