#include "plants.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=2*1e5+5;
struct node
{
int vl,id,lz;
node() {}
node(int _vl,int _id,int _lz)
{
vl=_vl;
id=_id;
lz=_lz;
}
};
node t[4*maxn];
node pull(node lf,node rt)
{
node h=lf;
if(lf.vl>rt.vl)h=rt;
return h;
}
void push(int i,int l,int r)
{
t[i].vl+=t[i].lz;
if(l!=r)
{
t[i*2].lz+=t[i].lz;
t[i*2+1].lz+=t[i].lz;
}
t[i].lz=0;
}
void updi(int i,int l,int r,int id,int vl)
{
push(i,l,r);
if(l==r)
{
t[i].vl=vl;
t[i].id=l;
return;
}
int m=(l+r)/2;
push(i*2,l,m);
push(i*2+1,m+1,r);
if(id<=m)updi(i*2,l,m,id,vl);
else updi(i*2+1,m+1,r,id,vl);
t[i]=pull(t[i*2],t[i*2+1]);
}
void updr(int i,int l,int r,int ql,int qr)
{
push(i,l,r);
if(ql>qr)return;
if(ql<=l&&r<=qr)
{
t[i].lz-=1;
push(i,l,r);
return;
}
int m=(l+r)/2;
updr(i*2,l,m,ql,min(qr,m));
updr(i*2+1,m+1,r,max(m+1,ql),qr);
t[i]=pull(t[i*2],t[i*2+1]);
}
node query(int i,int l,int r,int ql,int qr)
{
push(i,l,r);
if(ql>qr)return {maxn,0,0};
if(ql<=l&&r<=qr)return t[i];
int m=(l+r)/2;
return pull(query(i*2,l,m,ql,min(qr,m)),query(i*2+1,m+1,r,max(m+1,ql),qr));
}
int g[maxn];
int sz,num;
void init(int k, std::vector<int> r)
{
num=r.size();
sz=r.size();
for(int i=0; i<r.size(); i++)
updi(1,0,sz-1,i,r[i]);
while(1)
{
stack<int> s;
node x=query(1,0,sz-1,0,sz-1);
if(x.vl!=0)break;
s.push(x.id);
while(s.size())
{
int y=s.top();
node z=query(1,0,sz-1,max(0,y-k+1),y-1);
if(y-k+1<0)z=pull(z,query(1,0,sz-1,sz+(y-k+1),sz-1));
if(z.vl==0)s.push(z.id);
else
{
g[y]=num--;
updr(1,0,sz-1,max(0,y-k+1),y-1);
if(y-k+1<0)
updr(1,0,sz-1,sz+(y-k+1),sz-1);
updi(1,0,sz-1,y,maxn);
s.pop();
}
}
}
/*for(int i=0;i<r.size();i++)
cout<<g[i]<<" ";
cout<<endl;*/
}
int compare_plants(int x, int y)
{
if(g[x]<g[y])return -1;
return 1;
}
