#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3;
int r_arr[N], p[N], k, n;
struct Segment_Tree{
struct Node{
int mn;
array<int, 2> prev_zero;
Node(){}
Node(int mn, int i): mn(mn), prev_zero({i, 0}){}
friend Node merge(const Node &l, const Node &r){
Node ret;
ret.mn = min(l.mn, r.mn);
if(r.prev_zero[1] >= k) ret.prev_zero = r.prev_zero;
else if(l.prev_zero[1]) ret.prev_zero = l.prev_zero;
else ret.prev_zero = r.prev_zero;
return ret;
}
};
Node nd[4 * N];
int lp[4 * N];
void init(int i = 0, int l = 0, int r = n - 1){
if(l == r){
nd[i] = Node(r_arr[l], l);
return;
}
int mid = (l + r) >> 1;
init(2 * i + 1, l, mid);
init(2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
}
void push(int i, int l, int r){
nd[i].mn += lp[i];
if(l != r){
lp[2 * i + 1] += lp[i];
lp[2 * i + 2] += lp[i];
}
lp[i] = 0;
}
int query(int i = 0, int l = 0, int r = n - 1){
push(i, l, r);
return nd[i].prev_zero[0];
}
int get_next_zero(int s, int i = 0, int l = 0, int r = n - 1){
if(l > r) return n;
push(i, l, r);
if(r < s || nd[i].mn) return n;
if(l == r) return l;
int mid = (l + r) >> 1;
int l_val = get_next_zero(s, 2 * i + 1, l, mid);
if(l_val != n) return l_val;
return get_next_zero(s, 2 * i + 2, mid + 1, r);
}
int get_prev_zero(int s, int i = 0, int l = 0, int r = n - 1){
if(l > r) return -1;
push(i, l, r);
if(l > s || nd[i].mn) return -1;
if(l == r) return l;
int mid = (l + r) >> 1;
int r_val = get_prev_zero(s, 2 * i + 2, mid + 1, r);
if(r_val != -1) return r_val;
return get_prev_zero(s, 2 * i + 1, l, mid);
}
void update_prev_zero(int s, int i = 0, int l = 0, int r = n - 1){
if(l > r) return;
push(i, l, r);
if(l > s || r < s) return;
if(l == r){
nd[i].prev_zero = {s, s - get_prev_zero(s - 1, 0, 0, n - 1)};
return;
}
int mid = (l + r) >> 1;
update_prev_zero(s, 2 * i + 1, l, mid);
update_prev_zero(s, 2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
}
void update_zeroes(int l2, int r2, int i = 0, int l = 0, int r = n - 1){
if(l > r) return;
push(i, l, r);
if(nd[i].mn) return;
if(r < l2 || r2 < l) return;
if(l == r){
update_prev_zero(l, i, l, r);
return;
}
int mid = (l + r) >> 1;
update_zeroes(l2, r2, 2 * i + 1, l, mid);
update_zeroes(l2, r2, 2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
}
void change_value(int s, int val, int i = 0, int l = 0, int r = n - 1){
if(l > r) return;
push(i, l, r);
if(r < s || s < l) return;
if(l == r){
nd[i] = Node(val, s);
return;
}
int mid = (l + r) >> 1;
change_value(s, val, 2 * i + 1, l, mid);
change_value(s, val, 2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
}
void update(int l2, int r2, int val, int i = 0, int l = 0, int r = n - 1){
if(l > r) return;
push(i, l, r);
if(r < l2 || r2 < l) return;
if(l2 <= l && r <= r2){
lp[i]+=val;
push(i, l, r);
return;
}
int mid = (l + r) >> 1;
update(l2, r2, val, 2 * i + 1, l, mid);
update(l2, r2, val, 2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
}
} st;
struct Fenwick{
int a[N];
Fenwick(){}
void clear(){
fill(a, a + N, 0);
}
void update(int i, int v){
for(++i; i < N; i+=i&-i)
a[i] += v;
}
int query(int i){
int ans = 0;
for(++i; i >= 1; i-=i&-i)
ans += a[i];
return ans;
}
int query(int l, int r){
return query(r) - query(l - 1);
}
} f;
const int LOGN = 18;
int nxt[2][LOGN][N];
void init(int _k, vector<int> _r) {
k = _k;
n = _r.size();
for(int i = 0; i < _r.size(); ++i)
r_arr[i] = _r[i];
st.init();
st.update_zeroes(0, n - 1);
for(int i = n - 1; i >= 0; --i){
int idx = st.query();
p[idx] = i;
//cout << idx << " idx" << endl;
st.change_value(idx, n);
if(idx){
st.update(max(idx - (k - 1), 0), idx - 1, -1);
st.update_zeroes(max(idx - (k - 1), 0), idx - 1);
}
if(idx < k - 1){
st.update(n - ((k - 1) - idx), n - 1, -1);
st.update_zeroes(n - ((k - 1) - idx), n - 1);
}
int nxt = st.get_next_zero(idx + 1);
if(nxt != n) st.update_prev_zero(nxt);
}
set<array<int, 2>> s;
for(int i = n - 1; i > n - k; --i)
s.insert({p[i], i});
for(int i = 0; i < n; ++i){
auto it = s.lower_bound({p[i], 0});
if(it == s.end()) nxt[0][0][i] = -1;
else nxt[0][0][i] = (*it)[1];
int prev_i = (i - (k - 1) + n) % n;
s.erase({p[prev_i], prev_i});
s.insert({p[i], i});
}
s.clear();
for(int i = 0; i < k - 1; ++i)
s.insert({p[i], i});
for(int i = n - 1; i >= 0; --i){
auto it = s.lower_bound({p[i], 0});
if(it == s.end()) nxt[1][0][i] = -1;
else nxt[1][0][i] = (*it)[1];
int prev_i = (i + (k - 1)) % n;
s.erase({p[prev_i], prev_i});
s.insert({p[i], i});
}
for(int i = 1; i < LOGN; ++i)
for(int j = 0; j < n; ++j){
int &ans = nxt[0][i][j];
int node_2 = nxt[0][i - 1][j];
if(node_2 == -1){
ans = -1;
continue;
}
int node_3 = nxt[0][i - 1][node_2];
if(node_3 == -1){
ans = node_3;
continue;
}
if(i < node_2){
if(node_3 > node_2 || node_3 <= j) ans = -1;
else ans = node_3;
}
else{
if(node_3 > node_2 && node_3 <= j) ans = -1;
else ans = node_3;
}
}
for(int i = 1; i < LOGN; ++i)
for(int j = 0; j < n; ++j){
int &ans = nxt[1][i][j];
int node_2 = nxt[1][i - 1][j];
if(node_2 == -1){
ans = -1;
continue;
}
int node_3 = nxt[1][i - 1][node_2];
if(node_3 == -1){
ans = node_3;
continue;
}
if(i < node_2){
if(node_3 >= j && node_3 < node_2) ans = -1;
else ans = node_3;
}
else{
if(node_3 >= j || node_3 < node_2) ans = -1;
else ans = node_3;
}
}
//cout << "done preprocessing" << endl;
}
int get_dist(int x, int y){
return min(abs(x - y), min(abs(x + n - y), abs(y + n - x)));
}
bool connected(int x, int y){
if(get_dist(x, y) <= k - 1) return true;
if(p[x] > p[y]) swap(x, y);
int target = (y + (k - 1)) % n;
int curr_x = x;
for(int i = LOGN - 1; i >= 0; --i){
int cand = nxt[0][i][curr_x];
if(cand != -1){
if(curr_x < target){
if(cand < curr_x || target < cand)
curr_x = cand;
}
else{
if(target < cand && cand < curr_x)
curr_x = cand;
}
}
}
curr_x = nxt[0][0][curr_x];
if(curr_x != -1 && get_dist(y, curr_x) <= k - 1)
if(p[curr_x] <= p[y])
return true;
target = (y - (k - 1) + n) % n;
curr_x = x;
for(int i = LOGN - 1; i >= 0; --i){
int cand = nxt[1][i][curr_x];
if(cand != -1){
if(curr_x < target){
if(curr_x < cand && cand < target)
curr_x = cand;
}
else{
if(curr_x < cand || cand < target)
curr_x = cand;
}
}
}
curr_x = nxt[1][0][curr_x];
if(curr_x != -1 && get_dist(y, curr_x) <= k - 1)
if(p[curr_x] <= p[y])
return true;
return false;
}
int compare_plants(int x, int y) {
if(!connected(x, y)) return 0;
return (p[x] > p[y]) ? 1 : -1;
}
/*
4 3 2
0 1 1 2
0 2
1 2
*/
/*
4 2 2
0 1 0 1
0 3
1 3
*/
/*
4 3 2
1 1 0 2
0 1
0 2
*/
