#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
#define MAXN 200005
#define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr);
typedef pair<int, int> pii;
int N, K, R[MAXN];
int H[MAXN], nxt_r[MAXN][18], nxt_l[MAXN][18];
template <typename T>
struct SegTree{
int n_bits, TS, ST;
int range_l(int x){ return ((x<<(__builtin_clz(x)-31+n_bits)) ^ (1<<n_bits)) + 1; }
int range_r(int x){ return ((x<<(__builtin_clz(x)-31+n_bits) ^ ((1<<(__builtin_clz(x)-31+n_bits))-1)) ^ (1<<n_bits)) + 1; }
struct Value{
T value, lazysum;
};
vector<Value> tree;
SegTree(int arr[]){
n_bits = 32-__builtin_clz(N-1);
TS = 1 << n_bits+1; ST = TS/2-1;
tree.resize(TS, {0, 0});
for (int i=ST+1;i<TS;i++) tree[i].value = i-ST <= N ? arr[i-ST] : 1e9;
for (int i=ST;i;i--) tree[i].value = min(tree[i*2].value, tree[i*2+1].value);
}
void propagate(int n){
if (n <= ST){
tree[n*2].value += tree[n].lazysum, tree[n*2+1].value += tree[n].lazysum;
tree[n*2].lazysum += tree[n].lazysum, tree[n*2+1].lazysum += tree[n].lazysum;
}
tree[n].lazysum = 0;
}
void update(int n, int l, int r, const int &v){
int s = range_l(n), e = range_r(n);
if (l > r || e < l || r < s) return;
if (l <= s && e <= r){
tree[n].value += v, tree[n].lazysum += v;
return;
}
propagate(n);
update(n*2, l, r, v);
update(n*2+1, l, r, v);
tree[n].value = min(tree[n*2].value, tree[n*2+1].value);
}
int findzero(int n){
if (tree[n].value != 0) return 0;
propagate(n);
if (n > ST) return n-ST;
if (!tree[n*2].value) return findzero(n*2);
else if (!tree[n*2+1].value) return findzero(n*2+1);
else assert(0);
}
};
struct ZeroContainer{
set<int> pos, non_covered;
set<int>::iterator _left(set<int>::iterator it){
auto ret = it;
if (ret == pos.begin()) ret = pos.end();
return --ret;
}
set<int>::iterator _right(set<int>::iterator it){
auto ret = it; ret++;
if (ret == pos.end()) return pos.begin();
return ret;
}
void insert(int p){
auto it = pos.insert(p).first;
auto l = _left(it), r = _right(it);
if (l == it || (*it-*l+N)%N >= K) non_covered.insert(p);
if (r != it && (*r-*it+N)%N < K) non_covered.erase(*r);
}
void remove(int p){
auto it = pos.find(p);
auto l = _left(it), r = _right(it);
if (l != it && r != it && (l == r || (*r-*l+N)%N >= K)) non_covered.insert(*r);
pos.erase(it);
}
int pop_smallest(){
int ret = *non_covered.begin(); non_covered.erase(ret);
remove(ret);
return ret;
}
};
int go_left(int n, int d)
{ return (n - d%N - 1 + N)%N + 1; }
int go_right(int n, int d)
{ return (n + d%N - 1 + N)%N + 1; }
void init(int K, vector<int> r)
{
::K = K;
N = r.size();
for (int i=1;i<=N;i++) R[i] = r[i-1];
{
SegTree<int> segtree(R);
ZeroContainer zc;
for (int ord=N;ord;ord--){
for (;;){
int p = segtree.findzero(1);
if (!p) break;
zc.insert(p);
segtree.update(1, p, p, 1e9);
}
int x = zc.pop_smallest();
H[x] = ord;
segtree.update(1, max(1, x-K+1), x-1, -1);
if (x-K+1 < 1) segtree.update(1, N-(1-(x-K+1))+1, N, -1);
}
}
{
set <pii> s;
for (int i=1;i<=K;i++) s.insert({H[i], i});
for (int i=1;i<=N;i++){
auto it = s.lower_bound({H[i], 0});
if (it != s.begin()){
it--;
nxt_r[i][0] = (it->second - i + N) % N;
}
int t = (i+K-1)%N+1;
s.insert({H[t], t});
s.erase({H[i], i});
}
}
{
set <pii> s;
for (int i=1;i<K;i++) s.insert({H[i], i});
for (int i=1;i<=N;i++){
int t = (i+K-2)%N+1;
auto it = s.lower_bound({H[t], 0});
if (it != s.begin()){
it--;
nxt_l[t][0] = (t - it->second + N) % N;
}
s.insert({H[t], t});
s.erase({H[i], i});
}
}
for (int i=0;i+1<18;i++) for (int j=1;j<=N;j++){
nxt_l[j][i+1] = min(N+10, nxt_l[go_left(j, nxt_l[j][i])][i] + nxt_l[j][i]);
nxt_r[j][i+1] = min(N+10, nxt_r[go_right(j, nxt_r[j][i])][i] + nxt_r[j][i]);
}
}
bool has_left_path(int a, int b)
{
int d = (a-b+N)%N;
for (int i=18;i--;) if (d >= nxt_l[a][i]){
d -= nxt_l[a][i];
a = go_left(a, nxt_l[a][i]);
}
return (a-b+N)%N < K && H[a] >= H[b];
}
bool has_right_path(int a, int b)
{
int d = (b-a+N)%N;
for (int i=18;i--;) if (d >= nxt_r[a][i]){
d -= nxt_r[a][i];
a = go_right(a, nxt_r[a][i]);
}
return (b-a+N)%N < K && H[a] >= H[b];
}
int compare_plants(int a, int b)
{
a++; b++;
if (has_left_path(a, b) || has_right_path(a, b)) return 1;
if (has_left_path(b, a) || has_right_path(b, a)) return -1;
return 0;
}
