#include "plants.h"
#include <bits/stdc++.h>
using std::array;
using std::pair;
using std::vector;
template <class F>
struct fixed : private F {
explicit fixed(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
constexpr int INF = std::numeric_limits<int>::max() / 2;
constexpr int LOG = 18;
class lazysegtree {
int size, logn;
vector<pair<int, int>> data;
vector<int> lazy;
void apply(const int k, const int e) {
data[k].first += e;
if (k < size) {
lazy[k] += e;
}
}
void flush(const int k) {
if (lazy[k] != 0) {
apply(2 * k, lazy[k]);
apply(2 * k + 1, lazy[k]);
lazy[k] = 0;
}
}
void push(const int k) {
const int lsb = __builtin_ctz(k);
for (int d = logn; d > lsb; --d) {
flush(k >> d);
}
}
void fetch(const int k) {
data[k] = std::min(data[2 * k], data[2 * k + 1]);
}
void pull(int k) {
k >>= __builtin_ctz(k);
while (k > 1) {
fetch(k >>= 1);
}
}
public:
explicit lazysegtree(const vector<int>& vec) {
logn = 0;
while ((1 << logn) < (int)vec.size()) {
logn += 1;
}
size = 1 << logn;
data.resize(2 * size, {INF, INF});
for (int i = 0; i < (int)vec.size(); ++i) {
data[size + i] = {vec[i], i};
}
for (int i = size - 1; i > 0; --i) {
fetch(i);
}
lazy.resize(size);
}
void disable(int k) {
k += size;
for (int d = logn; d > 0; --d) {
flush(k >> d);
}
data[k] = {INF, INF};
while (k > 1) {
fetch(k >>= 1);
}
}
void subtract(int l, int r) {
l += size;
r += size;
push(l);
push(r);
const int lc = l, rc = r;
while (l < r) {
if (l & 1) apply(l++, -1);
if (r & 1) apply(--r, -1);
l >>= 1;
r >>= 1;
}
pull(lc);
pull(rc);
}
pair<int, int> fold(int l, int r) {
l += size;
r += size;
push(l);
push(r);
pair<int, int> ret = {INF, INF};
while (l < r) {
if (l & 1) ret = std::min(ret, data[l++]);
if (r & 1) ret = std::min(ret, data[--r]);
l >>= 1;
r >>= 1;
}
return ret;
}
pair<int, int> fold() const {
return data[1];
}
};
class rangemin {
int size;
vector<int> data;
public:
explicit rangemin(const int n) : size(n), data(2 * n, INF) {}
void chmin(int i, const int x) {
i += size;
while (i > 0) {
data[i] = std::min(data[i], x);
i >>= 1;
}
}
int fold(int l, int r) const {
l += size;
r += size;
int ret = INF;
while (l < r) {
if (l & 1) ret = std::min(ret, data[l++]);
if (r & 1) ret = std::min(ret, data[--r]);
l >>= 1;
r >>= 1;
}
return ret;
}
};
int N;
vector<int> order, rank;
array<vector<int>, 18> left, right;
int dist(const int i, const int j) {
return i <= j ? j - i : j - i + N;
}
int move_left(const int i, const int x) {
return i >= x ? i - x : i - x + N;
}
int move_right(const int i, const int x) {
return i + x < N ? i + x : i + x - N;
}
void init(int K, vector<int> R) {
N = (int)R.size();
lazysegtree seg(R);
order.reserve(N);
while ((int)order.size() < N) {
fixed([&](auto&& dfs, const int i) -> void {
while (true) {
int x, j;
if (i >= K - 1) {
std::tie(x, j) = seg.fold(i - (K - 1), i);
} else {
std::tie(x, j) = std::min(seg.fold(i - (K - 1) + N, N), seg.fold(0, i));
}
if (x == 0) {
dfs(j);
} else {
break;
}
}
if (i >= K - 1) {
seg.subtract(i - (K - 1), i);
} else {
seg.subtract(i - (K - 1) + N, N);
seg.subtract(0, i);
}
seg.disable(i);
order.push_back(i);
})(seg.fold().second);
}
rangemin min(N);
rank.resize(N);
left[0].resize(N);
right[0].resize(N);
for (int k = N - 1; k >= 0; --k) {
const int i = order[k];
rank[i] = k;
min.chmin(i, k);
{
int x;
if (i >= K - 1) {
x = min.fold(i - (K - 1), i);
} else {
x = std::min(min.fold(i - (K - 1) + N, N), min.fold(0, i));
}
left[0][i] = x == INF ? 0 : dist(order[x], i);
}
{
int x;
if (i + K <= N) {
x = min.fold(i + 1, i + K);
} else {
x = std::min(min.fold(0, i + K - N), min.fold(i + 1, N));
}
right[0][i] = x == INF ? 0 : dist(i, order[x]);
}
}
for (int k = 0; k + 1 < LOG; ++k) {
left[k + 1].resize(N);
right[k + 1].resize(N);
for (int i = 0; i < N; ++i) {
left[k + 1][i] = std::min(N - 1, left[k][move_left(i, left[k][i])] + left[k][i]);
right[k + 1][i] = std::min(N - 1, right[k][move_right(i, right[k][i])] + right[k][i]);
}
}
}
bool between(const int x, const int l, const int r) {
if (l <= r) {
return l <= x and x <= r;
} else {
return x <= r or l <= x;
}
}
int compare_plants(int x, int y) {
if (rank[x] > rank[y]) {
return -compare_plants(y, x);
}
int a = x, b = x;
for (int k = LOG - 1; k >= 0; --k) {
if (const int t = (a - left[k][a] % N + N) % N; !between(y, t, a)) {
a = t;
}
if (const int t = (b + right[k][b]) % N; !between(y, b, t)) {
b = t;
}
}
if (between(y, move_left(a, left[0][a]), a) and rank[a] < rank[y]) {
return 1;
}
if (between(y, b, move_right(b, right[0][b])) and rank[b] < rank[y]) {
return 1;
}
return 0;
}
