#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
int n;
struct gap {
int i, j; // gap from i -> j
bool operator<(const gap &other) const {
return (j - i) < (other.j - other.i);
};
int eval() {return j - i;}
};
struct node {
int mn, l, r; gap gp;
};
node merge(node &a, node &b) {
if (a.mn < b.mn) return a;
else if (a.mn > b.mn) return b;
return {a.mn, a.l, b.r, max({a.gp, b.gp, {a.r, b.l}})};
}
struct segtree {
private:
vector<node> seg, a;
vector<int> lazy;
int n;
public:
segtree(vector<int> &x) {
n = (int)x.size();
seg.resize(4 * n);
lazy.resize(4 * n);
a.resize(n);
gap inf = {(int)1e9, (int)-1e9};
for (int i = 0; i < n; i++) a[i] = {x[i], i, i, inf};
build(1, 0, n - 1);
}
void build(int i, int l, int r) {
if (l == r) {
seg[i] = a[l];
return;
}
int mid = (l + r) / 2;
build(i * 2, l, mid);
build(i * 2 + 1, mid + 1, r);
seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
}
void push(int i, int l, int r) {
seg[i].mn += lazy[i];
if (l == r) {
lazy[i] = 0;
return;
}
lazy[i * 2] += lazy[i];
lazy[i * 2 + 1] += lazy[i];
lazy[i] = 0;
}
node query(int i, int l, int r, int ql, int qr) {
push(i, l, r);
if (r < ql || qr < l) {
gap inf2 = {(int)1e9, (int)-1e9};
node bruh = {(int)1e9, (int)1e9, (int)1e9, inf2};
return bruh;
}
if (ql <= l && r <= qr) return seg[i];
int mid = (l + r) / 2;
node lft = query(i * 2, l, mid, ql, qr);
node rgt = query(i * 2 + 1, mid + 1, r, ql, qr);
return merge(lft, rgt);
}
void upd(int i, int l, int r, int ql, int qr, int qv) {
push(i, l, r);
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) {
lazy[i] += qv;
push(i, l, r);
return;
}
int mid = (l + r) / 2;
upd(i * 2, l, mid, ql, qr, qv);
upd(i * 2 + 1, mid + 1, r, ql, qr, qv);
seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
}
void build() {
build(1, 0, n - 1);
}
node query(int ql, int qr) {
return query(1, 0, n - 1, ql, qr);
}
void upd(int ql, int qr, int qv) {
if (ql > qr) return;
upd(1, 0, n - 1, ql, qr, qv);
}
};
// vector<int> getmins(segtree &st) {
// pair<int, int> ogmn = st.query(0, n - 1);
// vector<int> ans;
// while (st.query(0, n - 1).first == ogmn.first) {
// pair<int, int> cur = st.query(0, n - 1);
// ans.push_back(cur.second);
// st.upd(cur.second, cur.second, 2e9);
// }
// for (auto &x : ans) st.upd(x, x, -2e9);
// return ans;
// }
vector<int> inds;
void init(int k, vector<int> r) {
n = (int)r.size(); inds.resize(n);
segtree st(r); vector<int> order; // descending
for (int _ = 0; _ < n; _++) {
// vector<int> poss = getmins(st);
// // cout << "mins:\n";
// // for (auto &x : poss) cout << x << " ";
// // cout << '\n';
// assert((int)poss.size() <= 2);
// int pos = -1;
// for (int i = 0; i < (int)poss.size(); i++) {
// int prev = (i + (int)poss.size() - 1) % ((int)poss.size());
// if (poss[i] > poss[prev]) {
// if (poss[i] >= poss[prev] + k) {
// pos = poss[i];
// break;
// }
// } else {
// int y = (poss[prev] + k);
// if (y < n) {
// pos = poss[i];
// break;
// }
// y %= n;
// if (poss[i] >= y) {
// pos = poss[i];
// break;
// }
// }
// }
// if ((int)poss.size() == 1) pos = poss[0];
int pos = -1;
node nd = st.query(0, n - 1);
if (nd.gp.eval() >= k) {
pos = nd.gp.j;
} else {
pos = nd.l;
}
if (pos == -1) break;
assert(pos != -1);
order.push_back(pos);
st.upd(pos, pos, (int)2e9);
// remove previous k
if (pos - k + 1 >= 0) {
st.upd(pos - k + 1, pos - 1, -1);
} else {
st.upd(0, pos - 1, -1);
int back = (pos - k + 1 + n) % n;
st.upd(back, n - 1, -1);
}
}
// cout << "order:\n";
// for (auto &x : order) cout << x << " ";
// cout << '\n';
for (int i = 0; i < n; i++) inds[order[i]] = i;
}
int compare_plants(int x, int y) {
if (inds[x] < inds[y]) return 1;
else return -1;
// cout << "query" << mat[x][y] << " " << mat[y][x] << '\n';
// if (!mat[x][y] && !mat[y][x]) return 0;
// if (mat[x][y]) return 1;
// else return -1;
}
