#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> L;
vector<int> R;
void init(int k, vector<int> r) {
int n = r.size();
L.resize(n);
R.resize(n);
int high = n;
while (*min_element(r.begin(), r.end()) != 1e9) {
vector<int> order(n);
iota(order.begin(), order.end(), 0);
auto Cnt = [&](int i) {
int ret = 0, val = r[i];
for (int j = 0; j + 1 < k; j++) {
i -= 1;
if (i < 0) {
i += n;
}
ret += (r[i] == val);
}
return ret;
};
sort(order.begin(), order.end(), [&](int i, int j) {
if (r[i] != r[j]) {
return r[i] < r[j];
}
return Cnt(i) > Cnt(j);
});
//assert(Cnt(order[0]) == 0);
int ptr = 0;
while (ptr + 1 < n && r[order[ptr + 1]] == r[order[ptr]] && Cnt(order[ptr + 1]) == Cnt(order[ptr])) {
ptr += 1;
}
for (int i = 0; i <= ptr; i++) {
L[order[i]] = high - ptr;
R[order[i]] = high;
r[order[i]] = 1e9;
}
high -= (ptr + 1);
}
/*for (int i = 0; i < n; i++) {
cout << L[i] << " " << R[i] << '\n';
}*/
}
int compare_plants(int x, int y) {
if (L[x] > R[y]) {
return 1;
}
if (R[x] < L[y]) {
return -1;
}
return 0;
}
