#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
const int inf = 1e9 + 20;
int a[maxn];
pair<int, int> tree[maxn * 4];
int lazy[maxn * 4];
int pos[maxn];
int dp_left[maxn];
int dp_right[maxn];
int n, k;
bool cmp(pair<int, int> p1, pair<int, int> p2) {
if (p1.first != p2.first) {
return p1.first < p2.first;
}
else if (p1.second < p2.second && p2.second - p1.second + 1 <= k) {
return true;
}
else if (p1.second > p2.second && n - (p1.second - p2.second - 1) <= k) {
return true;
}
else {
return false;
}
}
void build(int id, int lt, int rt) {
if (lt == rt) {
tree[id] = make_pair(a[lt], lt);
return;
}
int mt = (lt + rt) / 2;
build(id * 2, lt, mt);
build(id * 2 + 1, mt + 1, rt);
tree[id] = min(tree[id * 2], tree[id * 2 + 1], cmp);
}
void update(int id, int lt, int rt, int ql, int qr, int add) {
if (lt == ql && rt == qr) {
tree[id].first += add;
lazy[id] += add;
return;
}
tree[id * 2].first += lazy[id];
lazy[id * 2] += lazy[id];
tree[id * 2 + 1].first += lazy[id];
lazy[id * 2 + 1] += lazy[id];
lazy[id] = 0;
int mt = (lt + rt) / 2;
if (qr <= mt) {
update(id * 2, lt, mt, ql, qr, add);
}
else if (ql >= mt + 1) {
update(id * 2 + 1, mt + 1, rt, ql, qr, add);
}
else {
update(id * 2, lt, mt, ql, mt, add);
update(id * 2 + 1, mt + 1, rt, mt + 1, qr, add);
}
tree[id] = min(tree[id * 2], tree[id * 2 + 1], cmp);
}
void init(int _k, vector<int> _a) {
n = _a.size();
k = _k;
for (int i = 0; i < n; i++) {
a[i] = k - 1 - _a[i];
}
if (k == 2) {
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
dp_right[i] = i;
for (int j = (i + n - 1) % n; j != i; j = (j + n - 1) % n) {
dp_right[j] = (a[j] ? dp_right[(j + 1) % n] : j);
}
break;
}
}
for (int i = 0; i < n; i++) {
if (a[(i + n - 1) % n] == 1) {
dp_left[i] = i;
for (int j = (i + 1) % n; j != i; j = (j + 1) % n) {
dp_left[j] = (!a[(j + n - 1) % n] ? dp_left[(j + n - 1) % n] : j);
}
break;
}
}
}
else {
build(1, 0, n - 1);
for (int i = 0; i < n; i++) {
int rt = tree[1].second;
int lt = (rt + n - (k - 1)) % n;
pos[rt] = i;
update(1, 0, n - 1, rt, rt, inf);
if (lt <= rt) {
update(1, 0, n - 1, lt, rt, -1);
}
else {
update(1, 0, n - 1, lt, n - 1, -1);
update(1, 0, n - 1, 0, rt, -1);
}
}
}
return;
}
bool check(int x, int y) {
if (dp_left[x] == dp_right[x]) {
return (dp_left[x] != x);
}
else if (dp_left[x] < dp_right[x]) {
return dp_left[x] <= y && y <= dp_right[x];
}
else {
return (y >= dp_left[x] || y <= dp_right[x]);
}
}
int compare_plants(int x, int y) {
if (k == 2) {
if (check(x, y)) {
return 1;
}
else if (check(y, x)) {
return -1;
}
else {
return 0;
}
}
else {
return (pos[x] > pos[y] ? 1 : -1);
}
}
