#include "plants.h"
#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define st first
#define nd second
using namespace std;
const int N=(1<<18);
int rtab[N+N], lazy[2*N];
int k;
void prop(int v){
if(v>=N || !lazy[v])return;
int l=v+v, r=l+1;
lazy[l]+=lazy[v];
lazy[r]+=lazy[v];
rtab[l]+=lazy[v];
rtab[r]+=lazy[v];
lazy[v]=0;
}
void add(int v, int L, int R, int l, int r, int c){
if(l==L && r==R){
lazy[v]+=c;
rtab[v]+=c;
return;
}
int M=(L+R)>>1;
prop(v);
if(l<=M)add(2*v, L, M, l, min(M, r), c);
if(r>M)add(2*v+1, M+1, R, max(l, M+1), r, c);
rtab[v]=max(rtab[2*v], rtab[2*v+1]);
}
int checkk(){
if(rtab[1]<k)return -1;
int v=1;
while(v<N){
prop(v);
if(rtab[2*v]==k)v=2*v;
else v=2*v+1;
}
return v-N;
}
int tab[N+N], lazy2[N+N];
void prop2(int v){
if(v>=N || !lazy2[v])return;
int l=v+v, r=l+1;
lazy2[l]+=lazy2[v];
lazy2[r]+=lazy2[v];
tab[l]+=lazy2[v];
tab[r]+=lazy2[v];
lazy2[v]=0;
}
void add2(int v, int L, int R, int l, int r, int c){
if(l==L && r==R){
lazy2[v]+=c;
tab[v]+=c;
return;
}
int M=(L+R)>>1;
prop2(v);
if(l<=M)add2(2*v, L, M, l, min(M, r), c);
if(r>M)add2(2*v+1, M+1, R, max(l, M+1), r, c);
tab[v]=max(tab[2*v], tab[2*v+1]);
}
int getmax(){
int v=1;
while(v<N){
prop2(v);
if(tab[2*v]>tab[2*v+1])v=2*v;
else v=v*2+1;
}
return v-N;
}
int maks[N+N];
void Set(int i, int val){
for(i+=N, maks[i]=val, i>>=1; i; i>>=1){
maks[i]=max(maks[2*i], maks[2*i+1]);
}
}
int find(int l, int r){
r++;
int ans=0;
for( l+=N, r+=N; l<r; l>>=1, r>>=1){
if(l&1)ans=max(maks[l++], ans);
if(r&1)ans=max(maks[--r], ans);
}
return ans;
}
vector<int> kol, gdzie;
const int K=18;
long long Left[K][N], Right[K][N];
int n;
void init(int _k, std::vector<int> r) {
n=r.size();
k=_k-1;
for(int i=0; i<n; i++){
rtab[N+i]=k-r[i];
}
for(int i=N-1; i>0; i--){
rtab[i]=max(rtab[i+i], rtab[i+i+1]);
}
//cerr<<rtab[1]<<" "<<k<<"\n";
gdzie.resize(n);
for(int i=0; i<n; i++){
//cerr<<i<<"\n";
int t=checkk();
while(t!=-1){
//cerr<<t<<"\n";
add(1, 0, N-1, t, t, -N);
add2(1, 0, N-1, t, t, N);
if(t<n-1)add2(1, 0, N-1, t+1, min(n-1, t+k), -1);
if(t+k>=n)add2(1, 0, N-1, 0, t+k-n, -1);
t=checkk();
}
t=getmax();
assert(tab[t+N]==N);
//cerr<<t<<"q\n";
add2(1, 0, N-1, t, t, -N);
if(t)add(1, 0, N-1, max(t-k, 0), t-1, 1);
if(t<k)add(1, 0, N-1, n+t-k, n-1, 1);
if(t<n-1)add2(1, 0, N-1, t+1, min(n-1, t+k), 1);
if(t+k>=n)add2(1, 0, N-1, 0, t+k-n, 1);
gdzie[t]=kol.size();
kol.pb(t);
}
for(int i=n-1; i>=0; i--){
int a=0;
int t=kol[i];
if(t)a=max(a, find(max(t-k, 0), t-1));
if(t<k)a=max(a, find(n+t-k, n-1));
if(a==0)Left[0][kol[i]]=n;
else Left[0][kol[i]]=(n-kol[n-a]+kol[i])%n;
a=0;
if(t<n-1)a=max(a, find( t+1, min(n-1, t+k)));
if(t+k>=n)a=max(a, find(0, t+k-n));
if(a==0)Right[0][kol[i]]=n;
else Right[0][kol[i]]=(n+kol[n-a]-kol[i])%n;
Set(kol[i], n-i);
//cout<<kol[i]<<" "<<Left[0][kol[i]]<<" "<<Right[0][kol[i]]<<"\n";
}
for(int j=1; j<K; j++){
for(int i=0; i<n; i++){
Left[j][i]=Left[j-1][i]+Left[j-1][((i-Left[j-1][i])%n+n)%n];
Right[j][i]=Right[j-1][i]+Right[j-1][(i+Right[j-1][i])%n];
//cout<<j<<" "<<i<<" "<<Left[j][i]<<" "<<Right[j][i]<<"\n";
}
}
}
int compare_plants(int x, int y){
int a=1, b=0;
if(gdzie[x]>gdzie[y])swap(x, y), a=-1;
int t=(n+x-y)%n, u=0;
for(int i=K-1; i>=0; i--){
if(u+Left[i][(n+x-u)%n]<=t){
u+=Left[i][(n+x-u)%n];
}
}
//cout<<x<<" "<<y<<" "<<u<<" "<<t<<"\n";
int s=(n+x-u)%n;
if(((n+s-y)%n<=k || (n+y-s)%n<=k) && gdzie[(n+x-u)%n]<=gdzie[y])b=1;
t=(n+y-x)%n, u=0;
for(int i=K-1; i>=0; i--){
if(u+Right[i][(u+x)%n]<=t){
u+=Right[i][(u+x)%n];
}
}
s=(n+x+u)%n;
if(((n+s-y)%n<=k || (n+y-s)%n<=k) && gdzie[(x+u)%n]<=gdzie[y])b=1;
return a*b;
}
