#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
constexpr int kLogN = 18;
constexpr int kMaxN = 2e5 + 10;
class LazySegTree {
struct Node {
int val = kInf;
int inc = 0;
};
const size_t n;
vector<Node> t;
static Node unite(const Node l, const Node r) {
Node ans{};
ans.val = min(l.val, r.val);
ans.inc = 0;
return ans;
}
void push(const int x, const int l, const int r) {
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
for (const int child : {x + 1, y}) {
t[child].val += t[x].inc;
t[child].inc += t[x].inc;
}
t[x].inc = 0;
}
void build(const int x, const int l, const int r, const vector<int> &a) {
if (l == r) {
t[x].val = a[l];
t[x].inc = 0;
return;
}
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
build(x + 1, l, mid, a);
build(y, mid + 1, r, a);
t[x] = unite(t[x + 1], t[y]);
}
int find_last_zero(const int x, const int l, const int r, const int ql, const int qr) {
if (l == r) {
return l;
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
int ans = -1;
if (ql <= mid and t[x + 1].val == 0) {
ans = max(ans, find_last_zero(x + 1, l, mid, ql, qr));
}
if (mid < qr and t[y].val == 0) {
ans = max(ans, find_last_zero(y, mid + 1, r, ql, qr));
}
return ans;
}
void update(const int x, const int l, const int r, const int ql, const int qr, const int value) {
if (ql <= l and r <= qr) {
t[x].val += value;
t[x].inc += value;
return;
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (ql <= mid) {
update(x + 1, l, mid, ql, qr, value);
}
if (mid < qr) {
update(y, mid + 1, r, ql, qr, value);
}
t[x] = unite(t[x + 1], t[y]);
}
Node query(const int x, const int l, const int r, const int ql, const int qr) {
if (ql <= l and r <= qr) {
return t[x];
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (qr <= mid) {
return query(x + 1, l, mid, ql, qr);
} else if (mid < ql) {
return query(y, mid + 1, r, ql, qr);
} else {
return unite(query(x + 1, l, mid, ql, qr),
query(y, mid + 1, r, ql, qr));
}
}
public:
explicit LazySegTree(const vector<int> &a) : n(a.size()), t(2 * n - 1) {
build(0, 0, (int) n - 1, a);
}
int find_last_zero(const int l, const int r) {
return find_last_zero(0, 0, (int) n - 1, l, r);
}
void update(const int l, const int r, const int x) {
update(0, 0, (int) n - 1, l, r, x);
}
int query(const int l, const int r) {
return query(0, 0, (int) n - 1, l, r).val;
}
};
//Global Variables
int n = 0;
int k = 0;
int h[kMaxN];
int left_dist[kMaxN][kLogN];
int right_dist[kMaxN][kLogN];
void find_valid_arrangement(vector<int> r) {
r.insert(r.end(), r.begin(), r.end());
int tall = n - 1;
LazySegTree st(r);
auto point_update = [&](const int i) {
st.update(i, i, kInf);
st.update(i - n, i - n, kInf);
};
auto range_update = [&](int i) {
st.update(i - k + 1, i, -1);
i -= n;
const int j = i - k + 1;
st.update(max(0, j), i, -1);
if (j < 0) st.update(2 * n + j, 2 * n - 1, -1);
};
function<void(int)> find_height = [&](const int i) {
while (st.query(i - k + 1, i - 1) == 0) {
const int j = st.find_last_zero(i - k + 1, i - 1);
find_height((j < n ? j + n : j));
}
h[i - n] = tall--;
point_update(i);
range_update(i);
};
while (tall >= 0) {
const int i = st.find_last_zero(n, 2 * n - 1);
find_height(i);
}
}
bool can_go_left(int x, const int y) {
int d = (x >= y ? x - y : x + n - y);
for (int j = kLogN - 1; j >= 0; j--) {
if (d < left_dist[x][j]) continue;
d -= left_dist[x][j];
x = (x - left_dist[x][j] + n) % n;
}
return (d < k and h[x] >= h[y]);
}
bool can_go_right(int x, const int y) {
int d = (x <= y ? y - x : y + n - x);
for (int j = kLogN - 1; j >= 0; j--) {
if (d < right_dist[x][j]) continue;
d -= right_dist[x][j];
x = (x + right_dist[x][j]) % n;
}
return (d < k and h[x] >= h[y]);
}
bool can_go(const int s, const int t) {
return can_go_left(s, t) or can_go_right(s, t);
}
void init(const int _k, vector<int> r) {
n = (int) r.size();
k = _k;
find_valid_arrangement(r);
{
const auto r_ = r;
r.insert(r.end(), r_.begin(), r_.end());
r.insert(r.end(), r_.begin(), r_.end());
}
set<pair<int, int>> lt, rt;
lt.insert({-1, -1});
for (int i = n - k + 1; i < n; i++) {
lt.insert({h[i], i});
}
rt.insert({-1, -1});
for (int i = n + 1; i < n + k; i++) {
rt.insert({h[i % n], i});
}
for (int i = n; i < 2 * n; i++) {
const int x = i - n;
{
auto [_, y] = *prev(lt.lower_bound(make_pair(h[x], x)));
left_dist[x][0] = (y == -1 ? kInf : i - y);
}
{
auto [_, y] = *prev(rt.lower_bound(make_pair(h[x], x)));
right_dist[x][0] = (y == -1 ? kInf : y - i);
}
{
lt.erase({h[(i - k + 1) % n], i - k + 1});
rt.erase({h[(i + 1) % n], i + 1});
lt.insert({h[x], i});
rt.insert({h[(i + k) % n], i + k});
}
}
for (int j = 1; j < kLogN; j++) {
for (int x = 0; x < n; x++) {
if (left_dist[x][j - 1] >= kInf) continue;
const int prev = left_dist[x][j - 1];
const int mid = (x - (prev % n) + n) % n;
left_dist[x][j] = left_dist[x][j - 1] + left_dist[mid][j - 1];
}
}
for (int j = 1; j < kLogN; j++) {
for (int x = 0; x < n; x++) {
if (right_dist[x][j - 1] >= kInf) continue;
const int prev = right_dist[x][j - 1];
const int mid = (x + prev) % n;
right_dist[x][j] = right_dist[x][j - 1] + right_dist[mid][j - 1];
}
}
}
int compare_plants(int x, int y) {
if (can_go(x, y)) return 1;
if (can_go(y, x)) return -1;
return 0;
}
