#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;
vector<int> lz;
segtree2(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);
}
}
};
vector<int> ord,rev;
vector<int> ord2,rev2;
}
void init(int k, std::vector<int> r) {
int n=(int)r.size();
{
segtree T1(n);
segtree T2(n);
T1.init();
T2.init();
for(int i=0;i<n;i++){
T1.update(i,i,r[i]);
T2.update(i,i,inf);
}
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;
//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);
}
rev.resize(n);
for(int i=0;i<n;i++){
rev[ord[i]]=i;
}
}
{
segtree2 T1(n);
segtree2 T2(n);
T1.init();
T2.init();
for(int i=0;i<n;i++){
T1.update(i,i,r[i]);
T2.update(i,i,inf);
}
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;
//cout<<pos<<'\n';
ord2.push_back(pos);
T2.update(pos,pos,inf);
T2.add(pos+1,pos+k-1,-1);
T1.add(pos-k+1,pos-1,-1);
}
rev2.resize(n);
for(int i=0;i<n;i++){
rev2[ord2[i]]=i;
}
}
return;
}
int compare_plants(int x, int y) {
if(rev[x]<rev[y] and rev2[x]<rev2[y]) return 1;
else if(rev[y]<rev[x] and rev2[y]<rev2[x]) return -1;
return 0;
}
