#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
int n;
struct segtree {
private:
vector<pair<int, int>> 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);
for (int i = 0; i < n; i++) a[i] = {x[i], i};
build(1, 0, n - 1);
}
pair<int, int> merge(pair<int, int> &x, pair<int, int> &y) {
if (x.first < y.first) return x;
else if (x.first > y.first) return y;
return x;
}
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].first += lazy[i];
if (l == r) {
lazy[i] = 0;
return;
}
lazy[i * 2] += lazy[i];
lazy[i * 2 + 1] += lazy[i];
lazy[i] = 0;
}
pair<int, int> query(int i, int l, int r, int ql, int qr) {
push(i, l, r);
if (r < ql || qr < l) return {2e9, 2e9};
if (ql <= l && r <= qr) return seg[i];
int mid = (l + r) / 2;
pair<int, int> lft = query(i * 2, l, mid, ql, qr);
pair<int, int> 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);
}
pair<int, int> 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];
if (pos == -1) break;
assert(pos != -1);
order.push_back(pos);
st.upd(pos, pos, 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;
}
