#include "plants.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
int n;
struct Segtree{
pair<int, int> mn[800005];
int lz[800005];
void push(int id, int l, int r){
mn[id].ff += lz[id];
if(l != r){
lz[id << 1] += lz[id];
lz[id << 1 | 1] += lz[id];
}
lz[id] = 0;
}
void build(int id, int l, int r, vector<int>& v){
if(l == r){
mn[id] = {v[l], l};
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m, v);
build(id << 1 | 1, m + 1, r, v);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}
void update(int id, int l, int r, int L, int R, int x){
if(L <= l && r <= R){
lz[id] += x;
push(id, l, r);
return;
}
push(id, l, r);
if(l > R || r < L) return;
int m = (l + r) >> 1;
update(id << 1, l, m, L, R, x);
update(id << 1 | 1, m + 1, r, L, R, x);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}
pair<int, int> query(int id, int l, int r, int L, int R){
push(id, l, r);
if(l > R || r < L)
return {1'000'000, 1};
if(L <= l && r <= R)
return mn[id];
int m = (l + r) >> 1;
return min(query(id << 1, l, m, L, R), query(id << 1 | 1, m + 1, r, L, R));
}
} s, t;
int le[200005], ri[200005];
vector<int> q;
int h[200005];
bool circle(int x, int y, int z){
if(x == z) return 0;
if(x <= y && y <= z)
return 1;
if(z <= x && x <= y)
return 1;
if(y <= z && z <= x)
return 1;
return 0;
}
void init(int k, std::vector<int> v) {
n = v.size();
for(auto& x : v)
x = k - 1 - x;
s.build(1, 0, n - 1, v);
for(auto& x : v)
x = 0;
t.build(1, 0, n - 1, v);
for(int i = 1; i <= n; ++i){
int now;
if(q.empty())
now = s.query(1, 0, n - 1, 0, n - 1).ss;
else {
now = q.back();
q.pop_back();
}
pair<int, int> tmp = min(s.query(1, 0, n - 1, max(0, now - k + 1), now - 1), s.query(1, 0, n - 1, now - k + 1 + n, n - 1));
while(tmp.ff == 0){
q.push_back(now);
now = tmp.ss;
tmp = min(s.query(1, 0, n - 1, now - k + 1, now - 1), s.query(1, 0, n - 1, now - k + 1 + n, n - 1));
}
s.update(1, 0, n - 1, now, now, 800'005);
s.update(1, 0, n - 1, now - k + 1, now - 1, -1);
s.update(1, 0, n - 1, now - k + 1 + n, n - 1, -1);
h[now] = i;
tmp = min(t.query(1, 0, n - 1, now - k + 1, now - 1), t.query(1, 0, n - 1, now - k + 1 + n, n - 1));
le[now] = tmp.ff == 0 ? now : circle(le[tmp.ss], now, tmp.ss) ? (now + 1) % n : le[tmp.ss];
tmp = min(t.query(1, 0, n - 1, now - k + 1, now - 1), t.query(1, 0, n - 1, now - k + 1 + n, n - 1));
ri[now] = tmp.ff == 0 ? now : circle(tmp.ss, now, ri[tmp.ss]) ? (n - 1 + now) % n : ri[tmp.ss];
t.update(1, 0, n - 1, now, now, -i);
}
}
int compare_plants(int x, int y) {
if(h[x] > h[y])
return 1;
return -1;
if(h[x] > h[y]) return -compare_plants(y, x);
if(circle(y, x, ri[y]) || circle(le[y], x, y))
return -1;
return 0;
}
