#include "plants.h"
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
using ll=int;
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>;
long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (200002)
int n, start, k;
vector<int> R;
ll A[MAXN*2];
inline int cy(ll x) {
if(x < 0) x += n;
if(x >= n) x -= n;
return x;
}
int dist(int x,int y) {
if(x > y) swap(x, y);
return min(y-x, n-y+x);
}
struct node {
int s,e,m;
spi v;
ll lazy[3];
node*l,*r;
node(int S,int E){
s=S,e=E,m=(s+e)>>1;
v=spi(INF, pi(0, -1)), mmst(lazy, 0);
if(s^e)l=new node(s,m),r=new node(m+1,e),v=min(l->v,r->v);
else v=spi(R[s], pi(0, s));
}
void value() {
v.f += lazy[0], v.s.f += lazy[1];
if(s^e) FOR(i,0,1) l->lazy[i]+=lazy[i], r->lazy[i]+=lazy[i];
lazy[0]=lazy[1]=0;
}
void update(int x,int y,pi nval,pi nval2=pi(0, 0)) {
if(s==x&&e==y) {
if(nval.s <= 1) lazy[nval.s] += nval.f;
else lazy[nval.s] = max(lazy[nval.s], nval.f);
if(nval2.s <= 1) lazy[nval2.s] += nval2.f;
else lazy[nval2.s] = max(lazy[nval2.s], nval2.f);
return;
}
if(x>m) r->update(x,y,nval,nval2), r->value();
else if(y<=m) l->update(x,y,nval,nval2), l->value();
else l->update(x,m,nval,nval2),r->update(m+1,y,nval,nval2), l->value(), r->value();
v=min(l->v,r->v);
}
spi rmq(int x,int y) {
value();
if(s==x&&e==y) return v;
if(x>m) return r->rmq(x,y);
else if(y<=m) return l->rmq(x,y);
else return min(l->rmq(x,m),r->rmq(m+1,y));
}
void set(int x,ll add=0) {
add = max(add, lazy[2]);
if(s==e) {
A[s] = add;
v = spi(INF, pi(0, -1));
return;
}
if(x>m) r->set(x, add);
else l->set(x, add);
v = min(l->v, r->v);
}
} *seg;
void update(int x,int y,pi nval,pi nval2=pi(0,0)) {
x=cy(x), y=cy(y);
if(x<=y) seg->update(x,y,nval,nval2);
else seg->update(x,n-1,nval,nval2), seg->update(0,y,nval,nval2);
}
spi rmq(int x,int y) {
x=cy(x), y=cy(y);
if(x<=y) return seg->rmq(x, y);
else return min(seg->rmq(x, n-1), seg->rmq(0, y));
}
struct node2 {
int s,e,m;
pi v;
node2*l,*r;
node2(int S,int E){
s=S,e=E,m=(s+e)>>1;
v = pi(-INF, -1);
if(s^e)l=new node2(s,m),r=new node2(m+1,e);
}
pi rmq(int x,int y) {
if(s==x&&e==y) return v;
if(x>m) return r->rmq(x, y);
else if(y<=m) return l->rmq(x, y);
else return max(l->rmq(x, m), r->rmq(m+1, y));
}
void set(int x) {
if(s==e) {
v = pi(A[s], s);
return;
}
if(x>m) r->set(x);
else l->set(x);
v = max(l->v, r->v);
}
} *seg2;
struct tree {
int p[18][MAXN*2];
bitset<MAXN*2> r;
vector<int> v[MAXN*2];
tree() {
mmst(p, 0), r.set();
}
void add(int x,int y) {
if(y==-1||x==y) return;
r[x]=0, v[y].eb(x);
}
void solve() {
function<void(ll)>dfs=[&](int x) {
for(auto i:v[x]) p[0][i]=x, dfs(i);
};
FOR(i,0,2*n-1) if(r[i]) p[0][i]=2*n, dfs(i);
FOR(j,1,17) FOR(i,0,2*n-1) if(p[j-1][i]==2*n) p[j][i]=2*n; else p[j][i]=p[j-1][p[j-1][i]];
}
inline int h(int x,int l) {
DEC(i,17,0) if(p[i][x] < l) x = p[i][x];
return p[0][x];
}
} t[2];
void init(int K, std::vector<int> r) { k=K, R=r;
n=r.size();
seg=new node(0, n-1);
FOR(i,0,n-1) if(r[i]==0) update(i+1, i+k-1, pi(1, 1));
while(1) {
start = seg->rmq(0, n-1).s.s;
if(start == -1) break;
seg->set(start);
update(start+1, start+k-1, pi(A[start]+1, 2), pi(-1, 1));
update(start-k+1, start-1, pi(A[start]+1, 2), pi(-1, 0));
vector<int> tmp;
while(1) {
spi x = rmq(start-k+1, start-1);
if(x.f == 0) {
tmp.eb(x.s.s);
update(x.s.s+1, x.s.s+k-1, pi(1, 1));
update(x.s.s, x.s.s, pi(1, 0));
} else break;
}
for(auto i:tmp) update(i, i, pi(-1, 0));
}
vector<int> p;
FOR(i,0,n-1) p.eb(i), p.eb(i+n), A[i+n]=A[i];
sort(all(p), [](int x,int y){return A[x]<A[y];});
seg2=new node2(0, 2*n-1);
for(auto i:p) {
int target = seg2->rmq(i, min(2*n-1, i+k-1)).s; // connect to shortest tower within k that is taller than you
t[0].add(i, target);
seg2->set(i);
}
reverse(all(p));
seg2=new node2(0, 2*n-1);
for(auto i:p) {
int target = seg2->rmq(i, min(2*n-1, i+k-1)).s;
t[1].add(i, target);
A[i]=-A[i], seg2->set(i), A[i]=-A[i];
}
FOR(i,0,1) t[i].solve();
}
int compare_plants(int x, int y) {
if(dist(x, y) < k) {
return A[x] < A[y] ? 1 : -1;
}
int i = t[0].h(x, y);
if(i <= y+k-1 && A[y] <= A[i]) {
return -1;
}
i = t[1].h(x, y);
if(i <= y+k-1 && A[y] >= A[i]) {
return 1;
}
swap(x, y);
y += n;
i = t[0].h(x, y);
if(i <= min(2*n-1, y+k-1) && A[y] <= A[i]) {
return 1;
}
i = t[1].h(x, y);
if(i <= min(2*n-1, y+k-1) && A[y] >= A[i]) {
return -1;
}
return 0;
}
