#include "plants.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
struct SegTree{
vector<pair<int,int>> t;
vector<int> lazy;
int n;
SegTree(int sz,vector<int> a){
n = sz;
t.assign(4*n,{0,0});
lazy.assign(4*n,0);
build(1,0,n-1,a);
}
void build(int v,int tl,int tr,vector<int> &a){
if(tl == tr){
t[v] = {a[tl],tl};
return;
}
int tm = (tl + tr)/2;
build(v*2,tl,tm,a);
build(v*2 + 1,tm+1,tr,a);
t[v] = t[v*2];
if(t[v*2 + 1].first < t[v].first)
t[v] = t[v*2+1];
}
void push(int v){
t[v*2].first += lazy[v];
lazy[v*2] += lazy[v];
t[v*2 + 1].first += lazy[v];
lazy[v*2 + 1] += lazy[v];
lazy[v] = 0;
}
void upd(int v,int tl,int tr,int l,int r,int val){
if(tr < l || r < tl)
return;
if(l <= tl && tr <= r){
t[v].first += val;
lazy[v] += val;
return;
}
push(v);
int tm = (tl + tr)/2;
upd(v*2,tl,tm,l,r,val);
upd(v * 2 + 1,tm+1,tr,l,r,val);
t[v] = t[v*2];
if(t[v*2 + 1].first < t[v].first)
t[v] = t[v*2+1];
}
pair<int,int> get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl)
return {1e9,0};
if(l <= tl && tr <= r){
return t[v];
}
push(v);
int tm = (tl + tr)/2;
auto a = get(v*2,tl,tm,l,r);
auto b = get(v*2+1,tm+1,tr,l,r);
if(b.first < a.first)
return b;
return a;
}
void upd(int l,int r,int val){
upd(1,0,n-1,l,r,val);
}
pair<int,int> get(int l,int r){
return get(1,0,n-1,l,r);
}
};
int k;
int a[N];
vector<int> adj[N];
int group[N];
bool ok[N];
int cnt = 1;
void dfs(int v){
cout << v << endl;
for(auto u:adj[v]){
group[u] = group[v];
dfs(u);
}
a[v] = cnt++;
}
int pre[N];
int n;
void init(int _k, vector<int> r) {
k = _k;
n = r.size();
if(k == 2){
for(int i = 0;i<n;i++){
pre[i] = r[i] + (i?pre[i-1]:0);
}
return;
}
SegTree t(n,r);
vector<int> x;
for(int i = n-1;i>=0;i--){
auto p1 = t.get(0,n-1);
auto p2 = t.get(p1.second + k,n-1);
if(p2.first == 0)
p1 = p2;
assert(p1.first == 0);
a[p1.second] = i;
if(p1.second)
t.upd(max(0,p1.second-k + 1),p1.second - 1,-1);
if(p1.second - k + 1 < 0){
t.upd(p1.second-k + 1 + n,n-1,-1);
}
t.upd(p1.second,p1.second,1e9);
// for(int j = 0;j<=n-1;j++){
// cout << t.get(j,j).first << ' ';
// }
// cout << endl;
// cout << i << ' ' << p1.second << endl;
}
// for(int i = n-1;i>=0;){
// vector<int> p;
// for(int j = 0;j<n;j++){
// if(t.get(j,j).first == 0)
// p.push_back(j);
// }
// vector<int> tmp;
// int maxi = -1e9;
// for(auto u:p){
// if(maxi + k - 1 < u)
// tmp.push_back(u);
// maxi = u;
// }
// int x = tmp.back() + k-1 - n;
// p.clear();
// for(auto u:tmp){
// if(u <= x)
// continue;
// p.push_back(u);
// }
// assert(p.size());
// for(auto u:p){
// if(u)
// t.upd(max(0,u-k + 1),u - 1,-1);
// if(u - k + 1 < 0){
// t.upd(u-k + 1 + n,n-1,-1);
// }
// t.upd(u,u,1e9);
// a[u] = i;
// }
// i -= p.size();
// }
}
int compare_plants(int x, int y) {
if(k == 2){
if(pre[y-1] - (x?pre[x-1]:0) == 0){
return 1;
}
if(pre[y-1] - (x?pre[x-1]:0) == y-x){
return -1;
}
if(pre[n-1] - (pre[y-1] - (x?pre[x-1]:0)) == 0){
return -1;
}
if(pre[n-1] - (pre[y-1] - (x?pre[x-1]:0)) == n - (y-x)){
return 1;
}
return 0;
}
if(a[x] > a[y])
return 1;
if(a[x] < a[y])
return -1;
return 0;
}
