#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=long long;
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 ll cy(ll x) {
x %= n, x += n, x %= n; return x;
}
ll 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(LLINF, 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) {
if(s==x&&e==y) {
if(nval.s <= 1) lazy[nval.s] += nval.f;
else lazy[nval.s] = max(lazy[nval.s], nval.f);
return;
}
if(x>m) r->update(x,y,nval);
else if(y<=m) l->update(x,y,nval);
else l->update(x,m,nval),r->update(m+1,y,nval);
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) {
value();
add = max(add, lazy[2]);
if(s==e) {
A[s] = add;
v = spi(LLINF, pi(0, -1));
return;
}
if(x>m) r->set(x, add);
else l->set(x, add);
l->value(), r->value();
v = min(l->v, r->v);
}
} *seg;
void update(int x,int y,pi nval) {
x=cy(x), y=cy(y);
if(x<=y) seg->update(x,y,nval);
else seg->update(x,n-1,nval), seg->update(0,y,nval);
}
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;
array<pi, 2> v;
node2*l,*r;
node2(int S,int E){
s=S,e=E,m=(s+e)>>1;
v = {pi(INF, -1), pi(-INF, -1)};
if(s^e)l=new node2(s,m),r=new node2(m+1,e);
}
array<pi, 2> comb(array<pi, 2> x,array<pi, 2> y) {
return array<pi, 2> {min(x[0], y[0]), max(x[1], y[1])};
}
array<pi, 2> 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 comb(l->rmq(x, m), r->rmq(m+1, y));
}
ll mx(int x,int y) {
if(x <= y) return rmq(x, y)[1].s;
else assert(0);
}
ll mi(int x,int y) {
if(x <= y) return rmq(x, y)[0].s;
else assert(0);
}
void set(int x) {
if(s==e) {
v = {pi(A[s], s), pi(A[s], s)};
return;
}
if(x>m) r->set(x);
else l->set(x);
v = comb(l->v, r->v);
}
} *seg2;
struct tree {
int st[MAXN*2], en[MAXN*2];
bitset<MAXN*2> r;
vector<int> v[MAXN*2];
tree() {
mmst(st, 0), mmst(en, 0), r.set();
}
void add(int x,int y) {
if(y==-1||x==y) return;
r[x]=0, v[y].eb(x);
}
void solve() {
ll co=1;
function<void(ll)>dfs=[&](int x) {
st[x]=co++;
for(auto i:v[x]) dfs(i);
en[x]=co-1;
};
FOR(i,0,n-1) if(r[i]) dfs(i);
}
bool isp(int a,int b) { return st[a]<=st[b]&&en[a]>=en[b]; }
} 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));
update(start+1, start+k-1, pi(-1, 1));
update(start-k+1, start-1, pi(A[start]+1, 2));
update(start-k+1, start-1, 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));
}
/* dp[0][0]=dp[1][0]=1;
FOR(i,0,1) fw[i].update(A[0], 1);
FOR(i,1,n-1) {
// FOR(jj,i-k+1,i-1) { int j=cy(jj);
// assert(A[i] ^ A[j]);
// if(A[i] < A[j]) dp[0][i] |= dp[0][j];
// else dp[1][i] |= dp[1][j];
// }
if(i >= k) FOR(j,0,1) if(dp[j][i-k]) fw[j].update(A[i-k], -1);
dp[0][i] = fw[0].sum(A[i]+1, MAXN-2) > 0;
dp[1][i] = fw[1].sum(0, A[i]-1) > 0;
FOR(j,0,1) if(dp[j][i]) fw[j].update(A[i], 1);
}
fw[0]=fen(), fw[1]=fen();
dp2[0][0]=dp2[1][0]=1;
FOR(i,0,1) fw[i].update(A[0], 1);
DEC(ii,-1,-n+1) { int i=cy(ii);
// FOR(jj,i+1,i+k-1) { int j=cy(jj);
// assert(A[i] ^ A[j]);
// if(A[i] < A[j]) dp2[0][i] |= dp2[0][j];
// else dp2[1][i] |= dp2[1][j];
// }
int t = cy(i + k);
if(t > i || t == 0) {
FOR(j,0,1) if(dp2[j][t]) fw[j].update(A[t], -1);
}
dp2[0][i] = fw[0].sum(A[i]+1, MAXN-2) > 0;
dp2[1][i] = fw[1].sum(0, A[i]-1) > 0;
FOR(j,0,1) if(dp2[j][i]) fw[j].update(A[i], 1);
} */
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->mx(i, min(2*n-1, i+k-1)); // connect to shortest tower within k that is taller than you
t[0].add(i, target);
seg2->set(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->mi(i, min(2*n-1, i+k-1));
t[1].add(i, target);
seg2->set(i);
}
// FOR(i,0,n-1) {
// int target = seg2->mi(i, i-k+1);
// t[2].add(i, target);
// }
// FOR(i,0,n-1) {
// int target = seg2->mx(i, i-k+1);
// t[3].add(i, target);
// }
FOR(i,0,1) t[i].solve();
}
int compare_plants(int x, int y) {
/* if(x == 0) {
if(dp[0][y] || dp2[0][y]) return -1;
else if(dp[1][y] || dp2[1][y]) return 1;
else return 0;
}
if(n > 300 || reach[x][y] || reach[y][x]) return A[x] < A[y] ? 1 : -1;
else return 0; */
if(dist(x, y) < k) {
return A[x] < A[y] ? 1 : -1;
}
FOR(i,y,y+k-1) {
if(A[y] <= A[i]) {
if(t[0].isp(i, x)) { if(0) assert(A[i] < A[x]); return -1; }
}
}
FOR(i,y,y+k-1) {
if(A[y] >= A[i]) {
if(t[1].isp(i, x)) { if(0) assert(A[x] < A[i]); return 1; }
}
}
swap(x, y);
y += n;
FOR(i,y,min(2*n-1, y+k-1)) {
if(A[y] <= A[i]) {
if(t[0].isp(i, x)) { if(0) assert(A[i] < A[x]); return 1; }
}
}
FOR(i,y,min(2*n-1, y+k-1)) {
if(A[y] >= A[i]) {
if(t[1].isp(i, x)) { if(0) assert(A[x] < A[i]); return -1; }
}
}
return 0;
}
