#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a), end(a)
using ar2 = array<int,2>;
const int mxN = (int)2e5+10;
const int INF = (int)1e9;
int n, h[mxN];
template<class T, int SZ> struct SegTree{
T seg[SZ], lzy[SZ];
void init(){ fill(seg,seg+SZ,0), fill(lzy,lzy+SZ,0); }
void prop(int p, int l, int r){
if(!lzy[p] or l==r) return;
int mid = (l+r)/2; int rp = p+2*(mid-l+1);
seg[p+1]+=lzy[p];
seg[rp]+=lzy[p];
lzy[p+1]+=lzy[p];
lzy[rp]+=lzy[p];
lzy[p]=0;
}
void upd(int i, int j, int v, int p=0, int l=0, int r=n-1){
if(i>r or j<l or i>j) return;
if(i<=l and r<=j){ seg[p]+=v; lzy[p]+=v; return; }
prop(p,l,r);
int mid = (l+r)/2; int rp = p+2*(mid-l+1);
if(i<=mid) upd(i,j,v,p+1,l,mid);
if(j>mid) upd(i,j,v,rp,mid+1,r);
seg[p] = min(seg[p+1],seg[rp]);
}
int findFirstMin(int i, int j, int p=0, int l=0, int r=n-1){
if(i>r or j<l or i>j) return -1;
prop(p,l,r);
if(l==r) return l;
int mid = (l+r)/2; int rp = p+2*(mid-l+1);
prop(p+1,l,mid);
if(seg[p+1]==seg[p]) return findFirstMin(i,j,p+1,l,mid);
return findFirstMin(i,j,rp,mid+1,r);
}
T query(int i, int p=0, int l=0, int r=n-1){
if(i<l or i>r) return INF; prop(p,l,r);
if(l==r) return seg[p];
int mid = (l+r)/2; int rp = p+2*(mid-l+1);
if(i<=mid) return query(i,p+1,l,mid);
return query(i,rp,mid+1,r);
}
};
const int mxSeg = 2*mxN;
SegTree<int,mxSeg> segTree;
void init(int k, vector<int> r) {
n = sz(r); k--; segTree.init();
for(int i = 0; i < n; i++) segTree.upd(i,i,r[i]);
for(int _ = n; _ > 0; _--){
int i = segTree.findFirstMin(0,n-1);
if(i<k){
segTree.upd(0,n-k+i-1,mxN);
int i1 = segTree.findFirstMin(0,n-1);
bool ok = 0;
if(i1!=-1 and !segTree.query(i1)) ok=1;
segTree.upd(0,n-k+i-1,-mxN);
if(ok) i=i1;
}
if(i>=k) segTree.upd(i-k,i-1,-1);
else segTree.upd(0,i-1,-1), segTree.upd(n-k+i,n-1,-1);
segTree.upd(i,i,mxN); h[i]=_;
}
}
int compare_plants(int x, int y) {
return h[x]>h[y]?1:-1;
}
