#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int v[maxn], lz[4*maxn], pd[maxn], n, ja[maxn];
pair<int,int> seg[4*maxn];
void build(int id, int ini, int fim){
if(ini==fim){
seg[id].first=0; seg[id].second=ini;
return;
}
int mid=(ini+fim)/2, e=2*id, d=2*id+1;
build(e,ini,mid); build(d,mid+1,fim);
lz[id]=0;
seg[id]=min(seg[e],seg[d]);
}
void refresh(int id, int ini, int fim){
if(ini!=fim){
int e=2*id, d=2*id+1;
lz[e]+=lz[id];
lz[d]+=lz[id];
}
seg[id].first+=lz[id];
lz[id]=0;
}
void update(int id, int ini, int fim, int l, int r, int val){
refresh(id,ini,fim);
if(ini>r||fim<l) return;
if(l<=ini&&fim<=r){
lz[id]+=val;
refresh(id,ini,fim);
return;
}
int mid=(ini+fim)/2, e=2*id, d=2*id+1;
update(e,ini,mid,l,r,val); update(d,mid+1,fim,l,r,val);
seg[id]=min(seg[e],seg[d]);
}
pair<int,int> query(int id, int ini, int fim, int l, int r){
if(ini>r||fim<l) return {maxn,maxn};
if(l<=ini&&fim<=r) return seg[id];
int mid=(ini+fim)/2, e=2*id, d=2*id+1;
return min(query(e,ini,mid,l,r),query(d,mid+1,fim,l,r));
}
int dist(int a, int b){
if(a==b) return maxn;
if(a<b) return b-a;
return b+1+(n-1-a);
}
void init(int k, vector<int> r){
//cout << "iniciado" << endl;
k--;
n=r.size();
build(1,0,n-1);
for(int i=0;i<n;i++) update(1,0,n-1,i,i,r[i]);
int cnt=maxn;
set<int>s;
vector<int>at, candidatos;
while(!query(1,0,n-1,0,n-1).first){ // enquanto tem cara com 0
int aux=query(1,0,n-1,0,n-1).second;
update(1,0,n-1,aux,aux,2*maxn); // settando pra inf
s.insert(aux);
auto f=s.upper_bound(aux);
if(f==s.end()) f=s.begin();
int qm=*f;
if(aux!=qm&&dist(aux,qm)<=k) pd[qm]=0; // vendo se bloqueio algm
auto g=s.lower_bound(aux);
if(g==s.begin()) g=s.end();
g--;
int ant=*g;
if(ant==aux||dist(ant,aux)>k) pd[aux]=1; // vendo se algm me bloqueia
candidatos.push_back(aux);
}
for(int x : candidatos){
if(pd[x]){
at.push_back(x);
s.erase(x);
}
}
// cout << "what " << at.size() << endl;
while(query(1,0,n-1,0,n-1).first<maxn||s.size()){
// cout << "! ";
// for(int x : at) cout << x << " ";
// cout << endl;
// cout << "? ";
// for(int x : s) cout << x << " ";
// cout << endl;
candidatos.clear();
for(int x : at){
v[x]=cnt;
if(x>=k) update(1,0,n-1,x-k,x-1,-1);
else{
update(1,0,n-1,0,x-1,-1);
update(1,0,n-1,n-(k-x),n-1,-1);
}
while(!query(1,0,n-1,0,n-1).first){ // enquanto tem cara com 0
int aux=query(1,0,n-1,0,n-1).second;
update(1,0,n-1,aux,aux,2*maxn); // settando pra inf
s.insert(aux);
auto f=s.upper_bound(aux);
if(f==s.end()) f=s.begin();
int qm=*f;
if(aux!=qm&&dist(aux,qm)<=k) pd[qm]=0; // vendo se bloqueio algm
auto g=s.lower_bound(aux);
if(g==s.begin()) g=s.end();
g--;
int ant=*g;
if(ant==aux||dist(ant,aux)>k) pd[aux]=1; // vendo se algm me bloqueia
candidatos.push_back(aux);
}
}
for(int x : at){
auto f=s.lower_bound(x);
if(f==s.end()) f=s.begin();
int aux=*f;
if(f==s.begin()) f=s.end();
f--;
int ant=*f;
//cout << "x " << ant << " " << aux << endl;
if(dist(ant,aux)>k){
//cout << "yep\n";
candidatos.push_back(aux);
pd[aux]=1;
}//else cout << "nope\n";
}
at.clear();
for(int x : candidatos){
if(pd[x]&&ja[x]==0){
ja[x]++;
at.push_back(x);
s.erase(x);
}
}
if(at.empty()){ // deu ciclo de inequacoes, ou seja, impossivel de decidir agr
for(int x : s) at.push_back(x);
s.clear();
}
cnt--;
}
// cout << query(1,0,n-1,0,n-1).first << endl;
// cout << "finish" << endl;
}
int compare_plants(int x, int y){
if(v[x]==v[y]) return 0;
if(v[x]<v[y]) return -1;
return 1;
}
