#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
const int inf = 1e9 + 20;
int a[maxn];
int tree[maxn * 4];
int lazy[maxn * 4];
int pos[maxn];
int dp_left[maxn];
int dp_right[maxn];
int n, k;
set<int> all_zeroes, good_zeroes;
void build(int id, int lt, int rt) {
if (lt == rt) {
tree[id] = a[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]);
}
void update(int id, int lt, int rt, int ql, int qr, int add) {
if (lt == ql && rt == qr) {
tree[id] += add;
lazy[id] += add;
return;
}
tree[id * 2] += lazy[id];
lazy[id * 2] += lazy[id];
tree[id * 2 + 1] += 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]);
}
bool contains(int x, int y) {
if (x < y) {
return y - x + 1 <= k;
}
else {
return n - (x - y - 1) <= k;
}
}
void add_zero(int x) {
auto it = all_zeroes.insert(x).first;
int prv = (it == all_zeroes.begin() ? *all_zeroes.rbegin() : *prev(it));
if (!contains(prv, x)) {
good_zeroes.insert(x);
}
/* int nxt = (next(it) == all_zeroes.end() ? *all_zeroes.begin() : *next(it));
if (contains(x, nxt)) {
good_zeroes.erase(nxt);
}
else {
good_zeroes.insert(nxt);
}*/
}
void rem_zero(int x) {
auto it = all_zeroes.find(x);
int prv = (it == all_zeroes.begin() ? *all_zeroes.rbegin() : *prev(it));
int nxt = (next(it) == all_zeroes.end() ? *all_zeroes.begin() : *next(it));
if (contains(prv, nxt)) {
good_zeroes.erase(nxt);
}
else {
good_zeroes.insert(nxt);
}
int rt = x;
int lt = (rt + n - (k - 1)) % n;
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);
}
all_zeroes.erase(it);
good_zeroes.erase(x);
}
void find_zeroes(int id, int lt, int rt) {
if (tree[id] > 0) {
return;
}
if (lt == rt) {
add_zero(lt);
tree[id] = inf;
lazy[id] = 0;
return;
}
tree[id * 2] += lazy[id];
lazy[id * 2] += lazy[id];
tree[id * 2 + 1] += lazy[id];
lazy[id * 2 + 1] += lazy[id];
lazy[id] = 0;
int mt = (lt + rt) / 2;
find_zeroes(id * 2, lt, mt);
find_zeroes(id * 2 + 1, mt + 1, rt);
tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
}
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++) {
find_zeroes(1, 0, n - 1);
pos[*good_zeroes.begin()] = i;
rem_zero(*good_zeroes.begin());
}
}
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);
}
}
