#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200'007
int prm[MAXN];
struct node
{
int mks;
int lm,rm;
int bdf,bdfi;
int lazy;
} seg[4*MAXN];
vector<int> rr;
void Push(int ind, bool ps)
{
if (seg[ind].lazy==0) return;
seg[ind].mks+=seg[ind].lazy;
if (!ps)
{
seg[ind].lazy=0;
return;
}
seg[ind*2].lazy+=seg[ind].lazy;
seg[ind*2+1].lazy+=seg[ind].lazy;
seg[ind].lazy=0;
}
void Merge(int ind, int l, int r)
{
Push(ind,1);
Push(ind*2,l!=(r-1));
Push(ind*2+1,l!=(r-1));
seg[ind].mks=max(seg[ind*2].mks,seg[ind*2+1].mks);
if (seg[ind*2].mks!=seg[ind].mks)
{
///copiram ot desniq
seg[ind].lm=seg[ind*2+1].lm;
seg[ind].rm=seg[ind*2+1].rm;
seg[ind].bdf=seg[ind*2+1].bdf;
seg[ind].bdfi=seg[ind*2+1].bdfi;
return;
}
if (seg[ind*2+1].mks!=seg[ind].mks)
{
///copiram ot leviq
seg[ind].lm=seg[ind*2].lm;
seg[ind].rm=seg[ind*2].rm;
seg[ind].bdf=seg[ind*2].bdf;
seg[ind].bdfi=seg[ind*2].bdfi;
return;
}
///actuali merge
seg[ind].lm=seg[ind*2].lm;
seg[ind].rm=seg[ind*2+1].rm;
if (seg[ind*2].bdf>seg[ind*2+1].bdf)
{
seg[ind].bdf=seg[ind*2].bdf;
seg[ind].bdfi=seg[ind*2].bdfi;
}
else
{
seg[ind].bdf=seg[ind*2+1].bdf;
seg[ind].bdfi=seg[ind*2+1].bdfi;
}
if ((seg[ind*2+1].lm-seg[ind*2].rm)>seg[ind].bdf)
{
seg[ind].bdf=seg[ind*2+1].lm-seg[ind*2].rm;
seg[ind].bdfi=seg[ind*2+1].lm;
}
}
void Initialise(int ind, int l, int r)
{
if (l==r)
{
seg[ind].mks=rr[l];
seg[ind].lm=l;
seg[ind].rm=l;
seg[ind].lazy=0;
seg[ind].bdf=-1;
seg[ind].bdfi=-1;
return;
}
int mid=(l+r)/2;
Initialise(ind*2,l,mid);
Initialise(ind*2+1,mid+1,r);
Merge(ind,l,r);
}
void Update(int ind, int l, int r, int ql, int qr)
{
Push(ind,l!=r);
if (ql<=l && qr>=r)
{
seg[ind].lazy+=1;
Push(ind,l!=r);
return;
}
int mid=(l+r)/2;
if (ql<=mid) Update(ind*2,l,mid,ql,qr);
if (qr>=mid+1) Update(ind*2+1,mid+1,r,ql,qr);
Merge(ind,l,r);
}
void Make0(int ind, int l, int r, int ch)
{
Push(ind,l!=r);
if (l==r && l==ch)
{
seg[ind].mks=0;
seg[ind].lm=l;
seg[ind].rm=l;
seg[ind].lazy=0;
seg[ind].bdf=-1;
seg[ind].bdfi=-1;
return;
}
int mid=(l+r)/2;
if (ch<=mid) Make0(ind*2,l,mid,ch);
else Make0(ind*2+1,mid+1,r,ch);
Merge(ind,l,r);
}
void init(int k, vector<int> r) {
int n=r.size();
rr=r;
Initialise(1,0,n-1);
for (int st=0;st<n;st++)
{
int spec=-1;
if (seg[1].bdf>=k)
{
spec=seg[1].bdfi;
//cout<<"edno\n";
}
else
{
spec=seg[1].lm;
//cout<<"dve\n";
}
prm[spec]=st;
//cout<<spec<<" "<<st<<"\n";
if (spec>=k-1)
{
Update(1,0,n-1,spec-k+1,spec-1);
//cout<<spec-k+1<<" "<<spec-1<<" e dob\n";
}
else
{
if (spec!=0) Update(1,0,n-1,0,spec-1);
int klk=(k-1)-spec;
Update(1,0,n-1,n-klk,n-1);
//if (spec!=0) cout<<0<<" "<<spec-1<<" e dob\n";
//cout<<n-klk<<" "<<n-1<<" e dob\n";
}
Make0(1,0,n-1,spec);
}
//for (int q=0;q<n;q++) cout<<prm[q]<<" ";
return;
}
int compare_plants(int x, int y) {
if (prm[x]>prm[y]) return 1;
return -1;
}
