#include "plants.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
const int inf=1e9;
int n;
struct segtree{
vector<pair<int,int>> st;
vector<int> lz;
segtree(int _n){
n=_n;
st=vector<pair<int,int>>(n*4);
lz=vector<int>(n*4);
}
void init(int l=0,int r=n-1,int v=1){
if(l==r){
st[v]={0,l};
return;
}
int mid=(l+r)/2;
init(l,mid,v*2);
init(mid+1,r,v*2+1);
st[v]=min(st[v*2],st[v*2+1]);
}
void push(int v){
st[v*2].f+=lz[v];
lz[v*2]+=lz[v];
st[v*2+1].f+=lz[v];
lz[v*2+1]+=lz[v];
lz[v]=0;
}
void update(int tl,int tr,int val,int l=0,int r=n-1,int v=1){
if(r<tl or tr<l){
return;
}
if(tl<=l and r<=tr){
st[v].f+=val;
lz[v]+=val;
return;
}
push(v);
int mid=(l+r)/2;
update(tl,min(mid,tr),val,l,mid,v*2);
update(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
st[v]=min(st[v*2],st[v*2+1]);
}
pair<int,int> query(int tl,int tr,int l=0,int r=n-1,int v=1){
if(r<tl or tr<l){
return {inf,-1};
}
if(tl<=l and r<=tr){
return st[v];
}
push(v);
int mid=(l+r)/2;
return min(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
}
void add(int l,int r,int val){
if(r<0){
l+=n;
r+=n;
}
if(l>=n){
l-=n;
r-=n;
}
if(l<0){
l+=n;
update(l,n-1,val);
update(0,r,val);
}
else if(r>=n){
r-=n;
update(l,n-1,val);
update(0,r,val);
}
else{
update(l,r,val);
}
}
};
struct segtree2{
vector<pair<int,int>> st;
segtree2(int _n){
n=_n;
st=vector<pair<int,int>>(n*4);
}
void init(int l=0,int r=n-1,int v=1){
if(l==r){
st[v]={0,l};
return;
}
int mid=(l+r)/2;
init(l,mid,v*2);
init(mid+1,r,v*2+1);
st[v]=max(st[v*2],st[v*2+1]);
}
void update(int pos,int val,int l=0,int r=n-1,int v=1){
if(l==r){
st[v].f+=val;
return;
}
int mid=(l+r)/2;
if(pos<=mid) update(pos,val,l,mid,v*2);
else update(pos,val,mid+1,r,v*2+1);
st[v]=max(st[v*2],st[v*2+1]);
}
pair<int,int> query(int tl,int tr,int l=0,int r=n-1,int v=1){
if(r<tl or tr<l){
return {-1,-1};
}
if(tl<=l and r<=tr){
return st[v];
}
int mid=(l+r)/2;
return max(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
}
int q(int l,int r){
if(l<=0 and r>=n-1){
l=0,r=n-1;
}
if(r<0){
l+=n;
r+=n;
}
if(l>=n){
l-=n;
r-=n;
}
if(l<0){
l+=n;
auto p=query(l,n-1);
p=max(p,query(0,r));
return (p.f==-1?-1:p.f);
}
else if(r>=n){
r-=n;
auto p=query(l,n-1);
p=max(p,query(0,r));
return (p.f==-1?-1:p.f);
}
else{
auto p=query(l,r);
return (p.f==-1?-1:p.f);
}
}
};
vector<int> ord,rev;
vector<int> st,en;
}
void init(int k, std::vector<int> r) {
int n=(int)r.size();
segtree T1(n);
segtree T2(n);
segtree2 T3(n);
vector<vector<int>>adj(n);
T1.init();
T2.init();
for(int i=0;i<n;i++){
T1.update(i,i,r[i]);
T2.update(i,i,inf);
T3.update(i,-1);
}
vector<int> par(n);
for(int t=0;t<n;t++){
while(T1.st[1].f==0){
int i=T1.st[1].s;
//cout<<"i "<<i<<'\n';
T1.update(i,i,inf);
T2.update(i,i,-inf);
T2.add(i+1,i+k-1,1);
}
int pos=T2.st[1].s;
int p=T3.q(pos,pos+k-1);
par[pos]=(p==-1?-1:ord[p]);
//cout<<(p==-1?-1:ord[p])<<' '<<pos<<'\n';
if(p!=-1) adj[ord[p]].push_back(pos);
//cout<<pos<<'\n';
ord.push_back(pos);
T2.update(pos,pos,inf);
T2.add(pos+1,pos+k-1,-1);
T1.add(pos-k+1,pos-1,-1);
T3.update(pos,(int)ord.size());
}
st=vector<int>(n);
en=vector<int>(n);
int timer=0;
function<void(int)> dfs=[&](int v){
st[v]=++timer;
for(auto u:adj[v]){
dfs(u);
}
en[v]=timer;
};
for(int i=0;i<n;i++){
if(par[i]==-1) dfs(i);
}
return;
}
int compare_plants(int x, int y) {
if(st[x]<=st[y] and en[y]<=en[x]) return 1;
else if(st[y]<=st[x] and en[x]<=en[y]) return -1;
return 0;
}
