#include<bits/stdc++.h>
#include "plants.h"
using namespace std;
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
const int MX=1e5+7;
pair<int,int> seg[4*MX];//maximo
int lz[4*MX];
void refresh(int pos, int ini, int fim){
if(lz[pos]==0)return;
seg[pos].first+=lz[pos];
if(ini==fim){
lz[pos]=0;return;
}
lz[2*pos]+=lz[pos];
lz[2*pos+1]+=lz[pos];
lz[pos]=0;
return;
}
pair<int,int> merge(pair<int,int> a, pair<int,int> b){
if(a.first==b.first)return make_pair(a.first,min(a.second,b.second));
else if(a.first>b.first)return a;
else return b;
}
void update(int pos, int ini, int fim, int l, int r,int val){
refresh(pos,ini,fim);
if(ini>r || fim<l)return;
if(l<= ini && fim<=r){
lz[pos]+=val;
refresh(pos,ini,fim);
return;
}
int m=(ini+fim)/2;
int e=2*pos,d=2*pos+1;
update(e,ini,m,l,r,val);
update(d,m+1,fim,l,r,val);
seg[pos]=merge(seg[e],seg[d]);
}
pair<int,int> query(int pos, int ini, int fim, int l, int r){
refresh(pos,ini,fim);
if(ini>r || fim<l)return {-1,-1};
if(l<= ini && fim<=r)return seg[pos];
int m=(ini+fim)/2;
return merge(query(2*pos,ini,m,l,r),query(2*pos+1,m+1,fim,l,r));
}
vector<int> val;
int n;
int k;
pair<int,int> build(int pos, int ini, int fim){
if(ini==fim){
return seg[pos]={val[ini],ini};
}
int m=(ini+fim)/2;
return seg[pos]=merge(build(2*pos,ini,m),build(2*pos+1,m+1,fim));
}
vector<int> ord;
int nxt2(int id){
if(id+k-1>n-1){
int x=id+k-1-n+1;
pair<int,int> p=query(1,0,n-1,id+1,n-1);
if(p.first==k-1)return p.second;
p=query(1,0,n-1,0,x-1);
if(p.first==k-1)return p.second;
return -1;
}
else{
pair<int,int> p=query(1,0,n-1,id+1,id+k-1);
if(p.first==k-1)return p.second;
else return -1;
}
}
int nxt(int id){
int mx=k-1;
pair<int,int> p=query(1,0,n-1,id+1,n-1);
if(p.first==mx)return p.second;
p=query(1,0,n-1,0,id-1);
if(p.first==mx)return p.second;
return -1;
}
pair<int,int> getlst(int id){
if(id>=k-1){
return query(1,0,n-1,id-k+1,id-1);
}
else{
int x=k-1-id;//vou ter que updatear esses x caras na frente
if(query(1,0,n-1,n-1-x+1,n-1).first!=k-1)return query(1,0,n-1,0,id-1);
else return query(1,0,n-1,n-1-x+1,n-1);
}
}
void updlst(int id){
if(id>=k-1){
update(1,0,n-1,id-k+1,id-1,1);
}
else{
int x=k-1-id;//vou ter que updatear esses x caras na frente
update(1,0,n-1,0,id-1,1);
update(1,0,n-1,n-1-x+1,n-1,1);
}
}
void init(int kk, std::vector<int> vec) {
k=kk;
n=sz(vec);
val=vec;
ord.resize(n);
build(1,0,n-1);
int goat=0;
vector<bool> marc(n,0);
L(i,0,n-1){
if(vec[i]==k-1){
goat=i;
int a=nxt2(i);
if(a!=-1)marc[a]=1;
}
}
L(i,0,n-1){
if(vec[i]==k-1 && marc[i]==0)goat=i;
}
int at=n;
const int MOD=1e9;
while(at>0){
if(goat==-1)return;
ord[goat]=at;
update(1,0,n-1,goat,goat,-MOD);
goat=nxt(goat);
while(getlst(goat).first==k-1)goat=getlst(goat).second;
at--;
}
//L(i,0,n-1)cout<<ord[i];
}
int compare_plants(int x, int y) {
if(ord[x]>ord[y])return -1;
else return 1;
}
