#include <bits/stdc++.h>
#include "plants.h"
#define ll long long
#define inf (ll) 1e17
using namespace std;
vector<ll> p;
ll n;
void printvec(vector<ll>& vec)
{
for (auto &&e : vec)
{
cout << e << ' ';
}
cout << endl;
}
ll maxn=2e5;
vector<ll> tree(4*maxn+4);
vector<ll> lazy(4*maxn+4);
void prop(ll node, ll l, ll r)
{
tree[node]+=lazy[node];
if(l==r)
{
lazy[node]=0;
return;
}
lazy[node*2+1]+=lazy[node];
lazy[node*2+2]+=lazy[node];
lazy[node]=0;
}
void update(ll node, ll l, ll r, ll x, ll y, ll val)
{
prop(node,l,r);
if(max(l,x) > min(r,y)) return;
if(x<=l && r<=y)
{
lazy[node]+=val;
prop(node,l,r);
return;
}
ll mid=(l+r)/2;
update(node*2+1,l,mid,x,y,val);
update(node*2+2,mid+1,r,x,y,val);
tree[node]=min(tree[node*2+1],tree[node*2+2]);
}
ll query(ll node, ll l, ll r, ll x, ll y)
{
prop(node,l,r);
if(max(l,x) > min(r,y)) return inf;
if(x<=l && r<=y)
{
return tree[node];
}
ll mid=(l+r)>>1;
return min(query(node*2+1,l,mid,x,y),query(node*2+2,mid+1,r,x,y));
}
void decrease(ll l, ll r)
{
if(l<=r)
{
update(0,0,n-1,l,r,-1);
}
else
{
update(0,0,n-1,l,n-1,-1);
if(r>=0)
update(0,0,n-1,0,r,-1);
}
}
ll findsmallest(ll l, ll r)
{
ll ans=-1;
ll oldl=l;
while(l<=r)
{
ll mid=(l+r)>>1;
ll vl=query(0,0,n-1,oldl,mid);
if(vl==0)
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
return ans;
}
ll findbiggest(ll l, ll r)
{
ll ans=-1;
ll oldr=r;
while(l<=r)
{
ll mid=(l+r)>>1;
ll vl=query(0,0,n-1,mid,oldr);
if(vl==0)
{
ans=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
return ans;
}
void init(int k, std::vector<int> r)
{
n=r.size();
p.resize(n);
vector<bool> vis(n);
for (int i=0;i<n;i++)
{
r[i]=k-1-r[i];
}
for (int i=0;i<n;i++)
{
update(0,0,n-1,i,i,r[i]);
}
for (int i=0;i<n;i++)
{
ll ind=findsmallest(0,n-1);
if(ind+k<n)
{
ll vl=findbiggest(ind+k,n-1);
if(vl!=-1)
{
ind=vl;
}
}
vis[ind]=true;
update(0,0,n-1,ind,ind,inf);
p[ind]=i;
decrease((ind-k+1+n)%n,ind-1);
}
}
int compare_plants(int x, int y)
{
if(p[x]<p[y]) return -1;
else return 1;
}
