#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 2e5 + 5, INF = 1e9;
int n, k;
arr<int, N> a;
int md(int i) { return ((i + n) % n == 0) ? n : (i + n) % n; }
arr<int, N> sm;
int qry_rng(int l, int r) {
if (l > r) return 0;
return sm[r] - sm[l - 1];
}
int qry(int i, int j) {
if (i <= j) return qry_rng(i, j);
return qry_rng(i, n) + qry_rng(1, j);
}
void sm_cmp() {
for (int i = 1; i <= n; i++)
sm[i] = sm[i - 1] + (a[i] == 0);
}
arr<bool, N> dn;
arr<vec<int>, N> adj;
void adj_cmp() {
for (int x = n; x >= 1; x--) {
sm_cmp();
int id = -1;
for (int i = 1; i <= n; i++) {
int y = (a[i] != 0) + qry(md(i - k + 1), md(i - 1));
if (y == 0) id = i;
}
assert(id != -1);
dn[id] = true;
for (int i = -k + 1; i <= k - 1; i++)
if (!dn[md(id + i)]) adj[id].push_back(md(id + i));
a[id] = INF;
for (int i = -k + 1; i <= -1; i++)
a[md(id + i)]--;
}
}
void init(int _k, vec<int> _a) {
n = _a.size(), k = _k;
for (int i = 1; i <= n; i++) a[i] = _a[i - 1];
adj_cmp();
// for (int u = 1; u <= n; u++) {
// cout << u << ": ";
// for (int v : adj[u]) cout << v << " ";
// cout << '\n';
// }
}
arr<bool, N> vs;
void dfs(int u) {
vs[u] = true;
for (int v : adj[u])
if (!vs[v]) dfs(v);
}
bool rch(int u, int v) {
vs.fill(false);
dfs(u);
return vs[v];
}
// 0 indexed
int compare_plants(int i, int j) {
i++, j++;
if (rch(i, j)) return 1;
else if (rch(j, i)) return -1;
return 0;
}
