#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define maxn 200200
#define inf 1000000
#define pii pair<int,int>
#define debug
#define pb push_back
int N;
int T[4*maxn];
int id[4*maxn];
int lazy[8*maxn];
int H[maxn];
void refresh(int ini,int fim,int p){
lazy[2*p] += lazy[p];
lazy[2*p+1] += lazy[p];
T[p] -= lazy[p];
lazy[p] = 0;
}
void upd(int ini,int fim,int p,int pos,int val){
refresh(ini,fim,p);
if(pos < ini || pos > fim) return;
if(ini == fim){
T[p] = val;
id[p] = pos;
return;
}
int mid = (ini+fim)/2;
upd(ini,mid,2*p,pos,val);
upd(mid+1,fim,2*p+1,pos,val);
if(T[2*p] < T[2*p+1]){
T[p] = T[2*p];
id[p] = id[2*p];
}
else {
T[p] = T[2*p+1];
id[p] = id[2*p+1];
}
}
void dec(int ini,int fim,int p,int l,int r){
refresh(ini,fim,p);
if(l > fim || r < ini)
return;
if(ini >= l && fim <= r){
lazy[p]++;
refresh(ini,fim,p);
return;
}
int mid = (ini+fim)/2;
dec(ini,mid,2*p,l,r);
dec(mid+1,fim,2*p+1,l,r);
if(T[2*p] < T[2*p+1]){
T[p] = T[2*p];
id[p] = id[2*p];
}
else {
T[p] = T[2*p+1];
id[p] = id[2*p+1];
}
}
vector<int> zeroes(){
vector<int> ret;
while(T[1] == 0){
int pos = id[1];
ret.pb(pos);
upd(0,N-1,1,pos,inf);
}
return ret;
}
set<pii> S;
set<pii> Si;
void add(int x){
S.insert({x,0});
}
void rem(int x){
auto it = S.lower_bound({x,-1});
S.erase(it);
}
int acha(){
debug("tem %d\n",(int)S.size());
int last = (*--S.end()).first-N;
int ans = 0, opt = 0;
for(auto i : S){
if(i.first - last > opt){
opt = i.first - last;
ans = i.first;
}
last = i.first;
}
return ans;
}
void go(int n, int k, int x, vector<int> r){
N = n;
for(int i=0;i<n;i++)
upd(0,N-1,1,i,r[i]);
int foi = 0;
while(foi < n){
vector<int> v = zeroes();
for(int i : v)
add(i);
//pii u = *--Si.end();
//int id = u.second;
int id = acha();
rem(id);
debug("pega %d\n",id);
H[id] = n-foi;
foi++;
dec(0,N-1,1,max(0,id-k+1),id-1);
if(id-k+1 < 0)
dec(0,N-1,1,id-k+1+N,N-1);
}
}
void init(int k, std::vector<int> r) {
go(r.size(), k, 0, r);
return;
}
int compare_plants(int x, int y) {
if(H[x] > H[y])
return 1;
else
return -1;
return 0;
}
