#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "plants.h"
namespace my {
const int N = 1 << 10;
int n, k, kth[N], can[N];
vector<int> g[N];
struct tree_t {
pair<int, int> mi[2 * N];
int pu[2 * N];
int ls(int v) {
return 2 * v + 1;
}
int rs(int v) {
return 2 * v + 2;
}
void build(int v, int l, int r) {
if (r - l == 1) {
mi[v] = mp(kth[l], l);
} else {
int m = (l + r) / 2;
build(ls(v), l, m);
build(rs(v), m, r);
mi[v] = min(mi[ls(v)], mi[rs(v)]);
}
}
void build() {
build(0, 0, N);
}
void push(int v) {
mi[ls(v)].x += pu[v];
mi[rs(v)].x += pu[v];
pu[ls(v)] += pu[v];
pu[rs(v)] += pu[v];
pu[v] = 0;
}
void upd(int v, int vl, int vr, int ql, int qr, int d) {
if (ql <= vl && vr <= qr) {
mi[v].x += d;
pu[v] += d;
return;
}
if (qr <= vl || vr <= ql) {
return;
}
push(v);
int vm = (vl + vr) / 2;
upd(ls(v), vl, vm, ql, qr, d);
upd(rs(v), vm, vr, ql, qr, d);
mi[v] = min(mi[ls(v)], mi[rs(v)]);
}
void range_add(int l, int r, int value) {
upd(0, 0, N, l, r, value);
}
void cycle_add(int from, int value) {
from %= n; from += n; from %= n;
if (from + k <= n) {
range_add(from, from + k, value);
} else {
range_add(from, n, value), range_add(0, from + k - n, value);
}
}
pair<int, int> query(int v, int vl, int vr, int ql, int qr) {
if (ql <= vl && vr <= qr) {
return mi[v];
}
if (qr <= vl || vr <= ql) {
return mp(N, -1);
}
int vm = (vl + vr) / 2;
push(v);
return min(query(ls(v), vl, vm, ql, qr), query(rs(v), vm, vr, ql, qr));
}
pair<int, int> range_min(int l, int r) {
return query(0, 0, N, l, r);
}
pair<int, int> cycle_min(int from) {
from %= n; from += n; from %= n;
if (from + k <= n) {
return range_min(from, from + k);
} else {
return min(range_min(from, n), range_min(0, from + k - n));
}
}
} tree;
void edge(int v, int u) {
assert(0 <= v && v < n);
assert(0 <= u && u < n);
// cout << "edge " << v << " " << u << endl;
g[v].push_back(u);
}
vector<int> topsort;
void extract(int v) {
tree.range_add(v, v + 1, N);
while (1) {
auto e = tree.cycle_min(v - k + 1);
if (e.x) break;
extract(e.y);
}
tree.cycle_add(v - k + 1, -1);
topsort.push_back(v);
}
void bfs(int v, bool used[N]) {
queue<int> q;
q.push(v);
used[v] = true;
while (q.size()) {
v = q.front(); q.pop();
for (int u : g[v]) {
if (!used[u]) {
q.push(u);
used[u] = true;
}
}
}
}
bool reach[N][N];
int lef[N], rig[N];
}
void init(int _k, vector<int> _r) {
using namespace my;
n = (int)_r.size();
k = _k;
copy(all(_r), kth);
tree.build();
while (1) {
auto e = tree.range_min(0, n);
if (e.x) break;
extract(e.y);
}
assert((int)topsort.size() == n);
reverse(all(topsort));
for (int i = 0; i < n; ++i) {
can[topsort[i]] = i;
}
set<pair<int, int>> iset;
for (int i = 0; i < k - 1; ++i) {
iset.emplace(can[i], i);
}
fill_n(lef, n, -1), fill_n(rig, n, -1);
for (int i = k - 1;;) {
auto it = iset.lower_bound(mp(can[i], i));
if (it != iset.begin()) {
--it;
lef[i] = it->y;
}
iset.erase({can[(i + n - k + 1) % n], (i + n - k + 1) % n});
iset.emplace(can[i], i);
(i += 1) %= n;
if (i == k - 1) break;
}
iset.clear();
for (int i = 0; i < k - 1; ++i) {
iset.emplace(can[i], i);
}
for (int i = n - 1; i >= 0; --i) {
auto it = iset.lower_bound(mp(can[i], i));
if (it != iset.begin()) {
--it;
rig[i] = it->y;
}
iset.erase({can[(i + k - 1) % n], (i + k - 1) % n});
iset.emplace(can[i], i);
}
// for (int i = 0; i < n; ++i) {
// cout << can[i] << " ";
// }
// cout << endl;
for (int i = 0; i < n; ++i) {
// cout << i << " " << lef[i] << " " << rig[i] << endl;
if (lef[i] != -1) {
edge(i, lef[i]);
}
if (rig[i] != -1) {
edge(i, rig[i]);
}
}
for (int i = 0; i < n; ++i) {
bfs(i, reach[i]);
}
}
int compare_plants(int x, int y) {
using namespace my;
if (reach[x][y]) {
return 1;
} else if (reach[y][x]) {
return -1;
} else {
return 0;
}
}
#ifdef LC
#include "grader.cpp"
#endif
