#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.second<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();
if (k==1)
{
a[0]=r[n-1];
for (int i=1;i<n;i++)
a[i]=a[i-1]+r[i-1];
}
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)
{
if (k==1)
{
int ml=1;
if (x>y) swap(x,y), ml=-1;
if (a[y]-a[x]==y-x) return ml*-1;
if (a[y]==a[x]) return ml;
if (a[x]+a[n-1]-a[y]==n-(y-x)) return ml;
if (a[x]+a[n-1]-a[y]==0) return ml*-1;
return 0;
}
return (a[x]>a[y])*2-1;
}
