#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
const int inf = 1e9;
int R[MAXN];
int n;
typedef pair<int, int> pii;
pii operator+(pii a, pii b) {
return pii(a.first+b.first, a.second+b.second);
}
class stree {
public:
int lp, rp;
stree *l = nullptr;
stree *r = nullptr;
int mn;
int lz = 0;
stree(int lp, int rp, bool tp) : lp(lp), rp(rp) {
if (lp < rp) {
int md = (lp+rp)/2;
l = new stree(lp, md, tp);
r = new stree(md+1, rp, tp);
mn = min(l->mn, r->mn);
}
else mn = tp ? R[lp] : inf;
}
void activate(int p) {
if (lp > p || rp < p) return;
if (lp == rp) {
mn = lz;
return;
}
prop();
l->activate(p);
r->activate(p);
mn = min(l->mn, r->mn);
}
void set_lz(int p) {
lz += p;
mn += p;
}
void prop() {
assert(l);
l->set_lz(lz);
r->set_lz(lz);
lz = 0;
}
int find() { // finds a position that is 0
if (mn > 0) return -1;
if (lp == rp) return lp;
prop();
int lq = l->find();
if (lq >= 0) return lq;
int v = r->find();
assert(v >= 0);
return v;
}
void del(int p) { // can be absorbed into find
if (lp > p || rp < p) return;
if (lp == rp) {
mn = inf;
return;
}
prop();
l->del(p); r->del(p);
mn = min(l->mn, r->mn);
}
void upd(int lv, int rv, int v) {
if (lp > rv || rp < lv) return;
if (lp >= lv && rp <= rv) {
set_lz(v);
return;
}
prop();
l->upd(lv, rv, v);
r->upd(lv, rv, v);
mn = min(l->mn, r->mn);
}
};
stree *tree[2];
int pos[MAXN];
void init(int k, vector<int> r) {
n = r.size();
for (int i = 0; i < n; i++) {
R[i] = r[i];
}
tree[0] = new stree(0, n-1, 0); // 0s to the left
tree[1] = new stree(0, n-1, 1); // rval
// for (int i = 0; i < n; i++) {
// if (r[i] == 0) {
// tree[0]->upd(i+1, min(n-1, i+k-1), pii(1, 0));
// if (i+k-1 >= n) tree[0]->upd(0, i+k-1-n, pii(1, 0));
// }
// }
for (int i = 0; i < n; i++) {
int f1;
while ((f1 = tree[1]->find()) >= 0) {
tree[0]->activate(f1);
tree[1]->del(f1);
tree[0]->upd(f1+1, min(n-1, f1+k-1), 1);
if (f1+k-1 >= n) tree[0]->upd(0, f1+k-1-n, 1);
}
int v = tree[0]->find();
assert(v != -1);
tree[0]->del(v);
pos[v] = i;
tree[0]->upd(v+1, min(n-1, v+k-1), -1);
tree[0]->upd(0, v+k-1-n, -1);
tree[1]->upd(max(0, v-k+1), v-1, -1);
if (v-k+1 < 0) tree[1]->upd(n+v-k+1, n-1, -1);
}
return;
}
int compare_plants(int x, int y) {
return 2*(pos[x]<pos[y])-1;
// if (x != (y+1)%n && y != (x+1)%n) return 0;
// if (x == (y+1)%n) return 2*(!lt[y])-1;
// return 2*lt[x]-1;
// if (x < y) {
// if (pre[y]-pre[x] == y-x) return -1;
// if (pre[x+n]-pre[y] == x+n-y) return 1;
// if (pre[y]-pre[x] == 0) return 1;
// if (pre[x+n]-pre[y] == 0) return -1;
// return 0;
// // }
return 0;
}
