#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
int n, k;
int ord[N], deg[N], dpl[N], dpr[N];
void init(int K, vector<int> r) {
n = r.size();
k = K;
if (k == 2) {
for (int i = 0;i < n;i++) {
if (r[i] == 1) deg[(i + 1) % n]++;
else deg[i]++;
}
for (int i = 0;i < n;i++) {
if (deg[i] != 0) continue;
dpl[i] = dpr[i] = 0;
for (int j = 1;j < n;j++) {
dpr[(i - j + n) % n] = j;
if (deg[(i - j + n) % n] == 2) break;
}
for (int j = 1;j < n;j++) {
dpl[(i + j) % n] = j;
if (deg[(i + j) % n] == 2) break;
}
}
return;
}
vector<vector<int>> pos(k);
for (int i = 0;i < n;i++) pos[r[i]].push_back(i);
memset(ord, -1, sizeof ord);
int tot = 0;
for (int i = k - 1;i >= 0;i--) {
auto p = pos[i];
int sz = p.size();
int idx = sz - 1;
for (int j = 0;j < sz - 1;j++) {
if (p[j + 1] - p[j] >= k) idx = j;
}
for (int j = 0;j < sz;j++) {
ord[p[(idx - j + sz) % sz]] = ++tot;
}
}
}
bool can(int x, int y) {
int l = dpr[x], r = dpl[x];
if (x + l >= n) {
if (x <= y || y <= x + l - n) return 1;
}
else {
if (x <= y && y <= x + l) return 1;
}
if (x - r < 0) {
if (y <= x || n + x - r <= y) return 1;
}
else {
if (x - r <= y && y <= x) return 1;
}
return 0;
}
int compare_plants(int x, int y) {
if (k != 2) return (ord[x] > ord[y]) ? 1 : -1;
if (can(x, y)) return 1;
if (can(y, x)) return -1;
return 0;
}
