#include "plants.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
vector<int> rk;
struct ST{
struct no{
pair<int,int> mn;
int tag=0;
};
vector<no> st;
void init(int x){
st.resize(4*x);
}
void build(int v,int L,int R,vector<int>& a){
if(L==R){
st[v].mn={a[L],L};
return;
}
int m=(L+R)/2;
build(2*v+1,L,m,a);
build(2*v+2,m+1,R,a);
st[v].mn=min(st[2*v+1].mn,st[2*v+2].mn);
}
void upd(int v,int t){
st[v].tag+=t;
st[v].mn.fs+=t;
}
void pudo(int v){
if(st[v].tag==0){
return;
}
upd(2*v+1,st[v].tag);
upd(2*v+2,st[v].tag);
st[v].tag=0;
}
void update(int v,int L,int R,int l,int r,int t){
if(l==L && r==R){
upd(v,t);
return;
}
pudo(v);
int m=(L+R)/2;
if(r<=m){
update(2*v+1,L,m,l,r,t);
}
else if(l>m){
update(2*v+2,m+1,R,l,r,t);
}
else{
update(2*v+1,L,m,l,m,t);
update(2*v+2,m+1,R,m+1,r,t);
}
st[v].mn=min(st[2*v+1].mn,st[2*v+2].mn);
}
pair<int,int> query(int v,int L,int R,int l,int r){
if(L==l && r==R){
return st[v].mn;
}
pudo(v);
int m=(L+R)/2;
if(r<=m){
return query(2*v+1,L,m,l,r);
}
else if(l>m){
return query(2*v+2,m+1,R,l,r);
}
else{
return min(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
}
}
}st;
int n;
void update(int l,int r){
if(l>r){
st.update(0,0,n-1,l,n-1,-1);
st.update(0,0,n-1,0,r,-1);
}
else{
st.update(0,0,n-1,l,r,-1);
}
}
void init(int k, vector<int> r) {
n=r.size();
rk.resize(n);
st.init(n);
st.build(0,0,n-1,r);
for(int i=0;i<n;i++){
auto h=st.query(0,0,n-1,0,n-1);
assert(h.fs==0);
int xl=(h.sc+1-k+n)%n,xr=(h.sc-1+n)%n;
if(xl>h.sc){
auto z=st.query(0,0,n-1,xl,n-1);
if(z.fs==0){
h=z;
}
}
xl=(h.sc+1-k+n)%n;
xr=(h.sc-1+n)%n;
rk[h.sc]=i;
update(xl,xr);
st.update(0,0,n-1,h.sc,h.sc,10000007);
}
return;
}
int compare_plants(int x, int y) {
return rk[x]<rk[y]?1:-1;
}
