#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
struct lazyseg{
int nl, nr;
int minnum = 1;
lazyseg* ln = nullptr;
lazyseg* rn = nullptr;
int lazy = 0;
lazyseg(int l, int r) : nl(l),nr(r){
if(l == r) return;
int mid = (+r)/2;
ln = new lazyseg(nl,mid);
rn = new lazyseg(mid+1,nr);
}
void extend(){
minnum += lazy;
if(ln != nullptr){
ln->lazy += lazy;
rn->lazy += lazy;
}
lazy = 0;
}
int update(int l, int r, int val){
if(r < nl || nr < l) return minnum;
if(l <= nl && nr <= r){
lazy += val;
return minnum + lazy;
}
extend();
return minnum = min(ln->update(l,r,val),rn->update(l,r,val));
}
int getnode(){
if(minnum != 0) return -1;
if(nl == nr) return nl;
extend();
int ret = ln->getnode();
if(ret != -1) return ret;
return rn->getnode();
}
};
struct segnode{
int nl, nr;
int maxnum = -1;
segnode* ln = nullptr;
segnode* rn = nullptr;
segnode(int l, int r) : nl(l), nr(r) {
if(nl == nr) return;
int mid = (nl + nr)/2;
ln = new segnode(nl,mid);
rn = new segnode(mid+1,nr);
}
void update(int x, int v){
if(x < nl || nr < x) return;
maxnum = max(maxnum, v);
if(ln != nullptr){
ln->update(x,v);
rn->update(x,v);
}
}
int queries(int l, int r){
if(r < nl || nr < l) return -1;
if(l <= nl || nr <= r) return maxnum;
return max(ln->queries(l,r),rn->queries(l,r));
}
};
void fix(int node, lazyseg& indeg, lazyseg& outdeg, int k, int n){
indeg.update(node,node,-1);
if(node + k >= n){
indeg.update(node+1,n,1);
indeg.update(0,node + k-n,1);
}
else{
indeg.update(node+1,node + k,1);
}
outdeg.update(node,node,k+3);
}
vector<int> t;
void init(int k, std::vector<int> r) {
int n = r.size();
t.resize(r.size(),-1);
int curt = 0;
lazyseg indeg(0,r.size()-1);
lazyseg outdeg(0,r.size()-1);
segnode tvals(0,r.size()-1);
for(int i = 0; i< n; i++){
outdeg.update(i,i,r[i]-1);
}
while(true){
int node = outdeg.getnode();
if(node == -1) break;
fix(node,indeg,outdeg,k,n);
}
while(true){
int node = indeg.getnode();
if(node == -1) break;
t[node] = curt++;
indeg.update(node,node,k+3);
if(node + k >= n){
indeg.update(node,n,-1);
indeg.update(0, node + k - n,-1);
}
else{
indeg.update(node,node+k,-1);
}
if(node < k){
outdeg.update(0,node,-1);
outdeg.update(n + node - k,n,-1);
}
else{
outdeg.update(node-k,node,-1);
}
while(true){
int node = outdeg.getnode();
if(node == -1) break;
fix(node,indeg,outdeg,k,n);
}
}
return;
}
int compare_plants(int x, int y) {
if(t[x] > t[y]) return -1;
else return 1;
return 0;
}
