#include <bits/stdc++.h>
struct Seg {
int size;
std::vector <int> lazy, min;
Seg(const std::vector <int> a) {
size = 1;
while (size < (int) a.size()) {
size <<= 1;
}
lazy.resize(size << 1, 0);
min.resize(size << 1, 1 << 30);
build(a);
}
inline void push(int now, int l, int r) {
min[now] += lazy[now];
if (r - l - 1) {
lazy[now * 2 + 1] += lazy[now];
lazy[now * 2 + 2] += lazy[now];
}
lazy[now] = 0;
}
inline void build(const std::vector <int>& a) {
build(a, 0, 0, a.size());
}
void build(const std::vector <int>& a, int now, int l, int r) {
if (!(r - l - 1)) {
min[now] = a[l];
return;
}
int mid = (l + r) >> 1;
build(a, now * 2 + 1, l, mid);
build(a, now * 2 + 2, mid, r);
min[now] = std::min(min[now * 2 + 1], min[now * 2 + 2]);
}
inline void update(int l, int r, int val) {
update(l, r, val, 0, 0, size);
}
void update(int tl, int tr, int val, int now, int l, int r) {
if (l >= tr || r <= tl) {
return;
}
if (l >= tl && r <= tr) {
lazy[now] += val;
push(now, l, r);
return;
}
int mid = (l + r) >> 1;
push(now, l, r);
update(tl, tr, val, now * 2 + 1, l, mid);
update(tl, tr, val, now * 2 + 2, mid, r);
min[now] = std::min(min[now * 2 + 1], min[now * 2 + 2]);
}
inline int find_last_zero(int l, int r) {
if (l == r) {
return -1;
}
return find_last_zero(l, r, 0, 0, size);
}
int find_last_zero(int tl, int tr, int now, int l, int r) {
if (l >= tr || r <= tl) {
return -1;
}
push(now, l, r);
if (min[now]) {
return -1;
}
if (!(r - l - 1)) {
return l;
}
int mid = (l + r) >> 1;
int right = find_last_zero(tl, tr, now * 2 + 2, mid, r);
return right == -1 ? find_last_zero(tl, tr, now * 2 + 1, l, mid) : right;
}
inline int find_first_zero(int l, int r) {
if (l == r) {
return -1;
}
return find_first_zero(l, r, 0, 0, size);
}
int find_first_zero(int tl, int tr, int now, int l, int r) {
if (l >= tr || r <= tl) {
return -1;
}
push(now, l, r);
if (min[now]) {
return -1;
}
if (!(r - l - 1)) {
return l;
}
int mid = (l + r) >> 1;
int left = find_first_zero(tl, tr, now * 2 + 1, l, mid);
return left == -1 ? find_first_zero(tl, tr, now * 2 + 2, mid, r) : left;
}
inline int query(int ind) {
return query(ind, 0, 0, size);
}
int query(int ind, int now, int l, int r) {
push(now, l, r);
if (!(r - l - 1)) {
return min[now];
}
int mid = (l + r) >> 1;
return ind < mid ? query(ind, now * 2 + 1, l, mid) : query(ind, now * 2 + 2, mid, r);
}
inline int query(int l, int r) {
return query(l, r, 0, 0, size);
}
int query(int tl, int tr, int now, int l, int r) {
if (l >= tr || r <= tl) {
return 1 << 30;
}
push(now, l, r);
if (l >= tl && r <= tr) {
return min[now];
}
int mid = (l + r) >> 1;
return std::min(query(tl, tr, now * 2 + 1, l, mid), query(tl, tr, now * 2 + 2, mid, r));
}
inline void set(int ind, int val) {
set(ind, val, 0, 0, size);
}
void set(int ind, int val, int now, int l, int r) {
if (!(r - l - 1)) {
lazy[now] = 0;
min[now] = val;
return;
}
int mid = (l + r) >> 1;
push(now, l, r);
ind < mid ? set(ind, val, now * 2 + 1, l, mid) : set(ind, val, now * 2 + 2, mid, r);
push(now * 2 + 1, l, mid);
push(now * 2 + 2, mid, r);
min[now] = std::min(min[now * 2 + 1], min[now * 2 + 2]);
}
};
int n, k;
std::vector <int> h;
std::vector <std::vector <int>> bin_left, bin_right;
void init(int _k, std::vector <int> r) {
n = r.size();
k = _k;
h.resize(n, -1);
Seg seg(r);
std::vector <int> ord;
auto f = [&] (auto&& self, int node) -> void {
int ind = -1;
do {
ind = -1;
if (node - k + 1 >= 0) {
ind = seg.find_last_zero(node - k + 1, node);
} else {
ind = seg.find_last_zero(0, node);
if (ind == -1) {
ind = seg.find_first_zero(n - ((k - 1) - node), n);
}
}
if (ind != -1) {
self(self, ind);
}
} while (ind != -1);
if (node - k + 1 >= 0) {
seg.update(node - k + 1, node + 1, -1);
} else {
seg.update(0, node + 1, -1);
seg.update(n - ((k - 1) - node), n, -1);
}
seg.update(node, node + 1, 1 << 30);
ord.push_back(node);
};
while (true) {
int v = seg.find_first_zero(0, n);
if (v == -1) {
break;
}
f(f, v);
}
assert((int) ord.size() == n);
for (int i = 0; i < n; i++) {
h[ord[i]] = n - i - 1;
}
std::vector <int> left(n, -1), right(n - 1);
Seg fseg(std::vector <int> (n, 1 << 30));
for (int i = n - 1; i >= 0; i--) {
int node = ord[i];
if (node - k + 1 >= 0) {
int val = fseg.query(node - k + 1, node);
left[node] = val < (1 << 30) ? ord[val] : -1;
} else {
int val = std::min(fseg.query(0, node), fseg.query(n - ((k - 1) - node), n));
left[node] = val < (1 << 30) ? ord[val] : -1;
}
if (node + k - 1 < n) {
int val = fseg.query(node + 1, node + k);
right[node] = val < (1 << 30) ? ord[val] : -1;
} else {
int val = std::min(fseg.query(node + 1, n), fseg.query(0, (k - 1) - (n - node - 1)));
right[node] = val < (1 << 30) ? ord[val] : -1;
}
fseg.set(node, i);
}
bin_left.resize(20, std::vector <int> (n, -1));
bin_right.resize(20, std::vector <int> (n, -1));
bin_left[0] = left;
bin_right[0] = right;
for (int b = 1; b < 20; b++) {
for (int i = 0; i < n; i++) {
bin_left[b][i] = bin_left[b - 1][i] == -1 ? -1 : bin_left[b - 1][bin_left[b - 1][i]];
bin_right[b][i] = bin_right[b - 1][i] == -1 ? -1 : bin_right[b - 1][bin_right[b - 1][i]];
}
}
}
inline bool contains(int from, int to, int target) {
if (from <= to) {
return from <= target && target <= to;
}
return contains(from, n - 1, target) || contains(0, to, target);
}
inline int dist(int from, int to) {
if (from <= to) {
return to - from;
}
return to + 1 + (n - from - 1);
}
bool greater(int u, int v) {
{
int ind = u;
int d = dist(v, u) - 1;
for (int b = 19; b >= 0; b--) {
if (bin_left[b][ind] != -1 && d - dist(bin_left[b][ind], ind) >= 0) {
ind = bin_left[b][ind];
d -= dist(bin_left[b][ind], ind);
}
}
int v1 = ind;
int v2 = bin_left[0][ind];
if (v2 != -1 && contains(v2, v1, v) && h[v1] > h[v]) {
return true;
}
}
{
int ind = u;
int d = dist(u, v) - 1;
for (int b = 19; b >= 0; b--) {
if (bin_right[b][ind] != -1 && d - dist(ind, bin_right[b][ind]) >= 0) {
ind = bin_right[b][ind];
d -= dist(ind, bin_right[b][ind]);
}
}
int v1 = ind;
int v2 = bin_right[0][ind];
if (v2 != -1 && contains(v1, v2, v) && h[v1] > h[v]) {
return true;
}
}
return false;
}
int compare_plants(int u, int v) {
if (greater(u, v)) {
return 1;
}
if (greater(v, u)) {
return -1;
}
return 0;
}
