#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 2e5 + 1;
int seg[M*2], id[M*2], lz[M*2], k, n, a[M];
void push(int v,int lc,int rc)
{
seg[lc]+=lz[v], lz[lc]+=lz[v];
seg[rc]+=lz[v], lz[rc]+=lz[v];
lz[v]=0;
}
void modify(int l,int r,int x,int v=0,int s=0,int e=n)
{
if (l>=e or r<=s) return;
if (l<=s && e<=r)
{
if (s+1==e) id[v]=s;
seg[v]+=x, lz[v]+=x;
return;
}
int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
push(v,lc,rc);
modify(l,r,x,lc,s,mid);
modify(l,r,x,rc,mid,e);
seg[v]=max(seg[lc],seg[rc]), id[v]=(seg[lc]>=seg[rc]?id[lc]:id[rc]);
}
pair<int,int> get(int l,int r,int v=0,int s=0,int e=n)
{
if (l>=e or r<=s) return {-1,-1};
if (l<=s && e<=r) return {seg[v],id[v]};
int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
push(v,lc,rc);
pair<int,int> p=get(l,r,lc,s,mid), p1=get(l,r,rc,mid,e);
if (p1.first>p.first) p=p1;
return p;
}
int find()
{
pair<int,int> p=get(0,n);
if (p.first<k)
{
pair<int,int> p1=get(n-(k-p.second),n);
if (p1.first==p.first)
{
p=p1;
while (1)
{
p1=get(p.second-k,p.second);
if (p1.first==p.first) p=p1;
else break;
}
return p.second;
}
}
return p.second;
}
void init(int K, vector<int> r)
{
k=K-1, n=r.size();
for (int i=0;i<n;i++)
modify(i,i+1,r[i]);
for (int i=0;i<n;i++)
{
int x=find();
a[x]=i, modify(x,x+1,-k);
modify(max(0,x-k),x,1);
if (x<k)
modify(n-(k-x),n,1);
}
return;
}
int compare_plants(int x, int y) {
return (a[x]>a[y])*2-1;
}
