#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 tam;
int res[N];
int n;
void erase(int pos){
seg.update(1,pos, pos, 1, n, -inf);
int r = pos;
int l = pos-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);
}
}
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;
}
n = r.size();
seg.build(1,1, n);
tam = r.size();
while(tam > 0){
vector <int> maximos;
pair <int, int> st = seg.query(1, 1, n, 1, n);
maximos.push_back(st.second);
while(true){
pair <int, int> nx = seg.query(1, maximos.back()+1, n, 1, n);
if(nx.first != st.first) break;
maximos.push_back(nx.second);
}
reverse(maximos.begin(), maximos.end());
set <int> s;
for(auto x : maximos) s.insert(x);
int best;
for(auto x : maximos){
best = x;
int l = max(1, x-k+1);
auto it = s.lower_bound(l);
int t = *it;
if(t == x) break;
}
for(auto x : maximos){
//cout << x << ' ';
if(x >= best){
res[x] = tam;
tam--;
erase(x);
}
}
reverse(maximos.begin(), maximos.end());
for(auto x : maximos){
if(x < best){
res[x] = tam;
tam--;
erase(x);
}
}
}
/*vector <int> debug;
for(int i = 1;i <= n;i++){
debug.push_back(res[i]);
}
d(debug);*/
return;
}
int compare_plants(int x, int y) {
if(res[x+1] < res[y+1]) return -1;
else return 1;
return 0;
}
