#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 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;
// }
for(int i = n-1;i>=0;){
vector<int> p;
for(int j = 0;j<n;j++){
if(t.get(j,j).first == 0)
p.push_back(j);
}
vector<int> tmp;
for(auto u:p){
if(tmp.empty() || tmp.back() + k - 1 < u)
tmp.push_back(u);
}
int x = tmp.back() + k-1 - n;
p.clear();
for(auto u:tmp){
if(u <= x)
continue;
p.push_back(u);
}
assert(p.size());
for(auto u:p){
if(u)
t.upd(max(0,u-k + 1),u - 1,-1);
if(u - k + 1 < 0){
t.upd(u-k + 1 + n,n-1,-1);
}
t.upd(u,u,1e9);
a[u] = i;
}
i -= p.size();
}
}
int compare_plants(int x, int y) {
if(a[x] > a[y])
return 1;
if(a[x] < a[y])
return -1;
return 0;
}
