#include "plants.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
struct SegTree{
vector<pair<int,int>> t;
vector<int> lazy;
int n;
SegTree(int sz,vector<int> a){
n = sz;
t.assign(4*n,{0,0});
lazy.assign(4*n,0);
build(1,0,n-1,a);
}
void build(int v,int tl,int tr,vector<int> &a){
if(tl == tr){
t[v] = {a[tl],tl};
return;
}
int tm = (tl + tr)/2;
build(v*2,tl,tm,a);
build(v*2 + 1,tm+1,tr,a);
t[v] = t[v*2];
if(t[v*2 + 1].first < t[v].first)
t[v] = t[v*2+1];
}
void push(int v){
t[v*2].first += lazy[v];
lazy[v*2] += lazy[v];
t[v*2 + 1].first += lazy[v];
lazy[v*2 + 1] += lazy[v];
lazy[v] = 0;
}
void upd(int v,int tl,int tr,int l,int r,int val){
if(tr < l || r < tl)
return;
if(l <= tl && tr <= r){
t[v].first += val;
lazy[v] += val;
return;
}
push(v);
int tm = (tl + tr)/2;
upd(v*2,tl,tm,l,r,val);
upd(v * 2 + 1,tm+1,tr,l,r,val);
t[v] = t[v*2];
if(t[v*2 + 1].first < t[v].first)
t[v] = t[v*2+1];
}
pair<int,int> get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl)
return {1e9,0};
if(l <= tl && tr <= r){
return t[v];
}
push(v);
int tm = (tl + tr)/2;
auto a = get(v*2,tl,tm,l,r);
auto b = get(v*2+1,tm+1,tr,l,r);
if(b.first < a.first)
return b;
return a;
}
void upd(int l,int r,int val){
upd(1,0,n-1,l,r,val);
}
pair<int,int> get(int l,int r){
return get(1,0,n-1,l,r);
}
};
int k;
int a[N];
void init(int k, vector<int> r) {
int n = r.size();
SegTree t(n,r);
// for(int j = 0;j<=n-1;j++){
// cout << t.get(j,j).first << ' ';
// }
// cout << endl;
for(int i = n-1;i>=0;i--){
auto p1 = t.get(0,n-1);
auto p2 = t.get(p1.second + k,n-1);
if(p2.first == 0)
p1 = p2;
assert(p1.first == 0);
a[p1.second] = i;
if(p1.second)
t.upd(max(0,p1.second-k + 1),p1.second - 1,-1);
if(p1.second - k + 1 < 0){
t.upd(p1.second-k + 1 + n,n-1,-1);
}
t.upd(p1.second,p1.second,1e9);
// for(int j = 0;j<=n-1;j++){
// cout << t.get(j,j).first << ' ';
// }
// cout << endl;
// cout << i << ' ' << p1.second << endl;
}
}
int compare_plants(int x, int y) {
if(a[x] > a[y])
return 1;
if(a[x] < a[y])
return -1;
return 0;
}
