#include"plants.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=200010;
struct seg
{
pi t[mx*4];
int lz[mx*4];
void init(int n,int s,int e,vector<int>&v)
{
lz[n]=0;
if(s==e)
{
t[n]=pi(v[s],s);
return;
}
int m=s+(e-s)/2;
init(n*2,s,m,v);
init(n*2+1,m+1,e,v);
t[n]=min(t[n*2],t[n*2+1]);
return;
}
inline void put(int n,int p)
{
t[n].fi+=p;
lz[n]+=p;
return;
}
inline void prop(int n)
{
if(lz[n]==0)
return;
put(n*2,lz[n]);
put(n*2+1,lz[n]);
lz[n]=0;
return;
}
void upd(int n,int s,int e,int S,int E,int p)
{
if(s>E||S>e)
return;
if(S<=s&&e<=E)
return put(n,p);
prop(n);
int m=s+(e-s)/2;
upd(n*2,s,m,S,E,p);
upd(n*2+1,m+1,e,S,E,p);
t[n]=min(t[n*2],t[n*2+1]);
return;
}
}st1,st2;
struct seg2
{
int t[mx*4];
void init(int n,int s,int e,int v)
{
t[n]=v;
if(s==e)
return;
int m=s+(e-s)/2;
init(n*2,s,m,v);
init(n*2+1,m+1,e,v);
return;
}
void put(int n,int s,int e,int x,int p)
{
if(s==e)
{
t[n]=p;
return;
}
int m=s+(e-s)/2;
if(x>m)
put(n*2+1,m+1,e,x,p);
else
put(n*2,s,m,x,p);
t[n]=min(t[n*2],t[n*2+1]);
return;
}
int query(int n,int s,int e,int S,int E)
{
if(s>E||S>e)
return inf;
if(S<=s&&e<=E)
return t[n];
int m=s+(e-s)/2;
return min(query(n*2,s,m,S,E),query(n*2+1,m+1,e,S,E));
}
}st3;
int ord[mx];
vector<int>ov;
int spa1[mx][20],spd1[mx][20];
int spa2[mx][20],spd2[mx][20];
int n;
void init(int k,vector<int>r)
{
n=r.size();
st1.init(1,0,n-1,r);
st2.init(1,0,n-1,r);
for(int i=0;i<n;i++)
{
while(st2.t[1].fi==0)
{
int cur=st2.t[1].se;
st2.upd(1,0,n-1,cur,cur,inf);
st1.upd(1,0,n-1,cur+1,cur+k-1,1),st1.upd(1,0,n-1,0,cur+k-1-n,1);
}
int cur=st1.t[1].se;
ord[cur]=i;
ov.eb(cur);
st1.upd(1,0,n-1,cur,cur,inf);
st1.upd(1,0,n-1,cur-k+1+n,n-1,-1),st1.upd(1,0,n-1,cur-k+1,cur-1,-1);
st1.upd(1,0,n-1,cur+1,cur+k-1,-1),st1.upd(1,0,n-1,0,cur+k-1-n,-1);
st2.upd(1,0,n-1,cur-k+1+n,n-1,-1),st2.upd(1,0,n-1,cur-k+1,cur-1,-1);
}
st3.init(1,0,n-1,n);
auto get3=[&](const int&p)->int{return min(st3.query(1,0,n-1,p-k+1,p-1),
st3.query(1,0,n-1,p-k+1+n,n-1));};
auto get4=[&](const int&p)->int{return min(st3.query(1,0,n-1,p+1,p+k-1),
st3.query(1,0,n-1,0,p+k-1-n));};
ov.eb(ord[n]=n);
for(int i=0;i<20;i++)
spa1[n][i]=spa2[n][i]=n,spd1[n][i]=spd2[n][i]=0;
for(int i=n;i-->0;)
{
int cur=ov[i];
int nx=ov[get3(cur)];
spa1[cur][0]=nx,spd1[cur][0]=nx>cur?1:0;
nx=ov[get4(cur)];
spa2[cur][0]=nx,spd2[cur][0]=nx<cur?1:0;
st3.put(1,0,n-1,cur,i);
}
for(int j=0;j<19;j++)
for(int i=0;i<=n;i++)
spa1[i][j+1]=spa1[spa1[i][j]][j],
spd1[i][j+1]=spd1[spa1[i][j]][j]+spd1[i][j],
spa2[i][j+1]=spa2[spa2[i][j]][j],
spd2[i][j+1]=spd2[spa2[i][j]][j]+spd2[i][j];
return;
}
int compare_plants(int x,int y)
{
int p=1;
if(ord[x]>ord[y])
swap(x,y),p=-1;
int l=x,ld=0;
int r=x,rd=0;
for(int i=20;i-->0;)
if(ord[spa1[l][i]]<=ord[y])
ld+=spd1[l][i],l=spa1[l][i];
for(int i=20;i-->0;)
if(ord[spa2[r][i]]<=ord[y])
rd+=spd2[r][i],r=spa2[r][i];
l-=n*min(2,ld),r+=n*min(2,rd);
for(int i=-1;i<=1;i++)
if(l+i*n<=y&&y<=r+i*n)
return p;
return 0;
}
