#include<bits/stdc++.h>
#include "plants.h"
#define fr first
#define sc second
using namespace std;
const int N = 200010;
const int inf = 1e8;
int k;
int v[N];
struct Segtree{
pair <int, int> tree[4*N];
int lazy[4*N];
void unlazy(int node, int l, int r){
tree[node].first += lazy[node];
if(l != r){
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
return;
}
pair <int, int> join(pair <int, int> a,pair <int, int> b){
if(a.fr > b.fr) return a;
if(a.fr < b.fr) return b;
if(a.sc < b.sc) return a;
return b;
}
void build(int node, int l, int r){
if(l == r){
tree[node] = {v[l], l};
lazy[node] = 0;
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
void update(int node, int l, int r, int tl, int tr, int val){
unlazy(node, tl, tr);
if(l <= tl and tr <= r){
lazy[node] += val;
unlazy(node, tl, tr);
return;
}
if(l > tr or tl > r) return;
int mid = (tl+tr)/2;
update(2*node, l, r, tl, mid, val);
update(2*node+1, l,r , mid+1, tr, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
pair <int, int> query(int node, int l, int r, int tl, int tr){
unlazy(node, tl, tr);
if(l > tr or tl > r) return {-inf, 0};
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l,r , mid+1, tr));
}
} seg;
int res[N];
void init(int K, std::vector<int> r){
k = K;
for(int i = 0;i < r.size();i++){
v[i+1] = k-r[i]-1;
}
int n = r.size();
seg.build(1,1, n);
int tam = r.size();
while(tam > 0){
pair <int, int> big = seg.query(1, 1, n, 1, n);
pair <int, int> big2 = seg.query(1, big.second+1, n, 1,n);
if(big2.first < big.first){
res[big.second] = tam;
seg.update(1,big.second, big.second, 1, n, -inf);
int r = big.second;
int l = big.second-k+1;
if(l > 0){
seg.update(1, l, r, 1, n, 1);
}
else{
seg.update(1, 1, r, 1, n, 1);
l += n;
seg.update(1, l, n, 1, n, 1);
}
}
else{
if(big.second <= big2.second and big2.second <= big.second+k-1){
res[big.second] = tam;
seg.update(1,big.second, big.second, 1, n, -inf);
int r = big.second;
int l = big.second-k+1;
if(l > 0){
seg.update(1, l, r, 1, n, 1);
}
else{
seg.update(1, 1, r, 1, n, 1);
l += n;
seg.update(1, l, n, 1, n, 1);
}
}
else{
res[big2.second] = tam;
seg.update(1,big2.second, big2.second, 1, n, -inf);
int r = big2.second;
int l = big2.second-k+1;
if(l > 0){
seg.update(1, l, r, 1, n, 1);
}
else{
seg.update(1, 1, r, 1, n, 1);
l += n;
seg.update(1, l, n, 1, n, 1);
}
}
}
tam--;
}
return;
}
int compare_plants(int x, int y) {
if(res[x+1] < res[y+1]) return -1;
else return 1;
return 0;
}
