#include <bits/stdc++.h>
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define m_p make_pair
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=2e5+1;
struct segtree{
pii t[4*N];
int p[4*N];
vec<int> a;
void push(int v,int tl,int tr){
for(auto &u : {v<<1,v<<1|1}){
t[u].f+=p[v];
p[u]+=p[v];
}
p[v]=0;
}
void build(int v,int tl,int tr){
p[v]=0;
if(tl==tr){
t[v]={a[tl],tl};
}
else{
int tm=(tl+tr)>>1;
build(v<<1,tl,tm);build(v<<1|1,tm+1,tr);
t[v]=min(t[v<<1],t[v<<1|1]);
}
}
void add(int l,int r,int x,int v,int tl,int tr){
if(tl>=l&&tr<=r){
t[v].f+=x;p[v]+=x;
// cout<<tl<<' '<<tr<<' '<<x<<' '<<t[v].f<<' '<<x<<endl;
return;
}
if(tl>r||tr<l) return;
int tm=(tl+tr)>>1;push(v,tl,tr);
add(l,r,x,v<<1,tl,tm);add(l,r,x,v<<1|1,tm+1,tr);
t[v]=min(t[v<<1],t[v<<1|1]);
}
pii get(int l,int r,int v,int tl,int tr){
if(tl>=l&&tr<=r) return t[v];
if(tl>r||tr<l) return m_p(1e9,-1);
int tm=(tl+tr)>>1;push(v,tl,tr);
return min(get(l,r,v<<1,tl,tm),get(l,r,v<<1|1,tm+1,tr));
}
}sega;
int n,k;
int h[N],it=0;
int _find(int i){
pii c;
if((i-k+1)<0){
int r=k-(i+1);
c=sega.get(n-r,n-1,1,0,n-1);
if(c.f>0){
c=sega.get(0,i-1,1,0,n-1);
}
}
else{
c=sega.get(i-k+1,i-1,1,0,n-1);
}
return (c.f<=0?c.s:-1);
}
int ht[N];
void place(int i){
sega.add(i,i,1e9,1,0,n-1);
int j=_find(i);
// cout<<"PLACE "<<i<<endl;
while(j!=-1){
place(j);
j=_find(i);
}
ht[i]=it++;
if((i-k+1)<0){
int r=k-(i+1);
sega.add(n-r,n-1,-1,1,0,n-1);
sega.add(0,i,-1,1,0,n-1);
}
else{
sega.add(i-k+1,i,-1,1,0,n-1);
}
}
int lft[N][20],rgt[N][20];
void init(int k, std::vector<int> r){
n=sz(r);::k=k;
sega.a=r;
sega.build(1,0,n-1);
fill(ht,ht+n,-1);
while(1){
pii c=sega.t[1];
if(c.f>0){
break;
}
int j=c.s;
place(j);
}
for(int i=0;i<n;i++) ht[i]=n-ht[i];
vec<int> ids(n);iota(all(ids),0);
sort(all(ids),[&](int i,int j){return ht[i]<ht[j];});
const int inf=(int)(1e9)-1;
for(int i=0;i<n;i++) sega.a[i]=inf;
sega.build(1,0,n-1);
for(auto &i : ids){
pii c=((i+1)>=k?sega.get(i-k+1,i-1,1,0,n-1):min(sega.get(0,i-1,1,0,n-1),sega.get(n-(k-(i+1)),n-1,1,0,n-1)));
if(c.f>=inf) lft[i][0]=0;
else lft[i][0]=(i+n-c.s)%n;
c=(i+k-1<n?sega.get(i+1,i+k-1,1,0,n-1):min(sega.get(i+1,n-1,1,0,n-1),sega.get(0,k-(n-i)-1,1,0,n-1)));
if(c.f>=inf) rgt[i][0]=0;
else rgt[i][0]=(c.s-i+n)%n;
sega.add(i,i,-inf-ht[i],1,0,n-1);
}
//
// for(int i=0;i<n;i++) cout<<i<<' '<<ht[i]<<' '<<lft[i][0]<<' '<<rgt[i][0]<<endl;
// cout<<endl;
for(int i=1;i<20;i++){
for(int j=0;j<n;j++){
lft[j][i]=lft[j][i-1]+lft[(j+n-lft[j][i-1])%n][i-1];
rgt[j][i]=rgt[j][i-1]+rgt[(j+rgt[j][i-1])%n][i-1];
if(lft[j][i]>=n) lft[j][i]=0;
if(rgt[j][i]>=n) rgt[j][i]=0;
}
}
// for(int i=0;i<n;i++){
// for(int j=0;j<20;j++)
// cout<<rgt[i][j]<<' ';
// }
}
int compare_plants(int x, int y){
int z=x;
for(int i=19;i>=0;i--){
if(rgt[z][i]<(y-z+n)%n)
z=(z+rgt[z][i])%n;
}
if(ht[z]>ht[y] && (y-z+n)%n<k) return 1;
z=y;
for(int i=19;i>=0;i--){
if(rgt[z][i]<(x-z+n)%n)
z=(z+rgt[z][i])%n;
}
if(ht[z]>ht[x] && (x-z+n)%n<k) return -1;
z=y;
for(int i=19;i>=0;i--){
if(lft[z][i]<(z-x+n)%n)
z=(z-lft[z][i]+n)%n;
}
if(ht[z]>ht[x] && (z-x+n)%n<k) return -1;
z=x;
for(int i=19;i>=0;i--){
if(lft[z][i]<(z-y+n)%n)
z=(z-lft[z][i]+n)%n;
}
if(ht[z]>ht[y] && (z-y+n)%n<k) return 1;
return 0;
}
/*
30 3 1
1 1 0 1 0 2 2 1 0 1 1 1 2 0 2 1 0 1 2 2 0 1 0 2 1 1 2 0 2 0
8 12
*/
