#include "plants.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=2*1e5+5;
int nn;
int lz[4*maxn];
int vl[4*maxn];
int id[4*maxn];
int a[maxn];
void pull(int i)
{
vl[i]=min(vl[i*2],vl[i*2+1]);
if(vl[i*2]<=vl[i*2+1])id[i]=id[i*2];
else id[i]=id[i*2+1];
}
void build(int i,int l,int r)
{
if(l==r)
{
vl[i]=a[l];
id[i]=l;
return;
}
int m=(l+r)/2;
build(i*2,l,m);
build(i*2+1,m+1,r);
pull(i);
//cout<<l<<" "<<r<<" "<<vl[i]<<" "<<id[i]<<endl;
}
void push(int i,int l,int r)
{
vl[i]-=lz[i];
if(l!=r)
{
lz[i*2]+=lz[i];
lz[i*2+1]+=lz[i];
}
lz[i]=0;
}
void update(int i,int l,int r,int ql,int qr)
{
push(i,l,r);
if(ql>qr)return;
if(ql<=l&&r<=qr)
{
lz[i]+=1;
push(i,l,r);
//cout<<"> "<<l<<" "<<r<<" "<<vl[i]<<" "<<id[i]<<endl;
return;
}
int m=(l+r)/2;
update(i*2,l,m,ql,min(qr,m));
update(i*2+1,m+1,r,max(m+1,ql),qr);
pull(i);
//cout<<"> "<<l<<" "<<r<<" "<<vl[i]<<" "<<id[i]<<endl;
}
pair<int,int> query(int i,int l,int r,int ql,int qr)
{
push(i,l,r);
if(ql>qr)return {1e9,1e9};
if(ql<=l&&r<=qr)return {vl[i],id[i]};
int m=(l+r)/2;
pair<int,int> q1=query(i*2,l,m,ql,min(qr,m));
pair<int,int> q2=query(i*2+1,m+1,r,max(m+1,ql),qr);
if(q1.first<=q2.first)return q1;
return q2;
}
void use(int i,int l,int r,int idx)
{
push(i,l,r);
if(idx>r||idx<l)return;
if(l==r)
{
vl[i]=1e9;
id[i]=l;
return;
}
int m=(l+r)/2;
use(i*2,l,m,idx);
use(i*2+1,m+1,r,idx);
pull(i);
}
int g[maxn];
void init(int k, std::vector<int> r)
{
for(int i=0;i<r.size();i++)
g[i]=0;
nn=r.size();
for(int i=0;i<r.size();i++)
a[i]=r[i];
for(int i=0;i<r.size();i++)
{
vector<int> h;
for(int j=0;j<r.size();j++)
{
if(g[j])continue;
if(a[j]==0)h.push_back(j);
}
if(h.size()==0)return;
int curr=h[0];
for(int j=1;j<h.size();j++)
{
if(h[j]-h[j-1]>k)
{
curr=h[j];
}
}
g[curr]=nn-i;
for(int j=1;j<=k;j++)
{
curr--;
if(curr==-1)curr=nn-1;
a[curr]--;
}
}
/*build(1,0,nn-1);
//cout<<"here"<<endl;
for(int i=0;i<r.size();i++)
{
//cout<<i<<"! "<<endl;
pair<int,int> p=query(1,0,nn-1,0,nn-1);
//cout<<p.first<<" "<<p.second<<endl;
if(p.second<k)
{
int lf=nn-(k-p.second);
pair<int,int> p1=query(1,0,nn-1,lf,nn-1);
if(p1.first==p.first)p=p1;
}
use(1,0,nn-1,p.second);
g[p.second]=nn-i;
update(1,0,nn-1,max(0,p.second-k),p.second-1);
//cout<<"- "<<max(0,p.second-k)<<" "<<p.second-1<<endl;
if(p.second<k)
{
int lf=nn-(k-p.second);
update(1,0,nn-1,lf,nn-1);
//cout<<"- "<<lf<<" "<<nn-1<<endl;
}
}*/
}
int compare_plants(int x, int y)
{
if(g[x]>g[y])return 1;
return -1;
}
