#ifdef LIS05ST
#define _GLIBCXX_DEBUG
#define _GLIBCXX_DEBUG_PEDANTIC
#endif
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,lzcnt")
#include"plants.h"
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
const int NMAX=2e6;
int pref[NMAX+5];
int n,k;
int get(int l,int r){
return pref[r]-pref[l-1];
}
bool one(int l,int r){
return get(l,r)==r-l+1;
}
bool zero(int l,int r){
return get(l,r)==0;
}
vector<int>h;
int id(int x){
return (x%n+n)%n;
}
struct Node{
int min;
int pos;
ll padd;
};
Node tree[4*NMAX+5];
Node merge(Node a,Node b){
Node res;
res.min=min(a.min,b.min);
res.pos=-1;
if(a.min==res.min){
res.pos=max(res.pos,a.pos);
}
if(b.min==res.min){
res.pos=max(res.pos,b.pos);
}
res.padd=0;
return res;
}
vector<int>vec;
void build(int v,int l,int r){
if(l==r){
tree[v].min=vec[l];
tree[v].pos=l;
tree[v].padd=0;
return;
}
int m=(l+r)/2;
build(2*v,l,m);
build(2*v+1,m+1,r);
tree[v]=merge(tree[2*v],tree[2*v+1]);
}
void pushAdd(int v,int val){
tree[v].min+=val;
tree[v].padd+=val;
}
void push(int v,int l,int r){
pushAdd(2*v,tree[v].padd);
pushAdd(2*v+1,tree[v].padd);
tree[v].padd=0;
}
pair<int,int> get(int v,int l,int r,int l0,int r0,bool p=1){
//if(p)cout<<l<<":"<<r<<" "<<l0<<":"<<r0<<"\n";
//if(p)cout<<tree[2*v].min<<" "<<tree[2*v].pos<<"\n";
push(v,l,r);
if(r0<l||r<l0||tree[v].min!=0)return {1e9,1e9};
if(l0<=l&&r<=r0&&l==r)return {tree[v].min,tree[v].pos};
int m=(l+r)/2;
if(tree[2*v].min==0&&tree[2*v].pos>=l0)return get(2*v,l,m,l0,r0,p);
return get(2*v+1,m+1,r,l0,r0,p);
}
void add(int v,int l,int r,int l0,int r0,int val){
push(v,l,r);
if(r0<l||r<l0)return;
if(l0<=l&&r<=r0){
pushAdd(v,val);
return;
}
int m=(l+r)/2;
add(2*v,l,m,l0,r0,val);
add(2*v+1,m+1,r,l0,r0,val);
tree[v]=merge(tree[2*v],tree[2*v+1]);
}
void add(int l,int r,int val){
l-=3*n;r-=3*n;
for(auto e:vector<int>{0,1,2,3,4,5,6,7,8}){
if(0<=r&&r<=3*n-1){
int L=min(3*n-1,max(l,0));
int R=min(3*n-1,max(r,0));
add(1,0,3*n-1,L,R,val);
}
else if(0<=l&&l<=3*n-1){
int L=min(3*n-1,max(l,0));
int R=min(3*n-1,max(r,0));
add(1,0,3*n-1,L,R,val);
}
l+=n;r+=n;
}
}
int step;
void extract(int pos){
while(true){
auto [a,b]=get(1,0,3*n-1,pos-k+1,pos-1);
if(a==0)extract(b);
else break;
}
h[pos%n]=step--;
add(pos-k+1,pos-1,-1);
add(pos,pos,1e9);
}
int lefte[30][NMAX+5];
int righte[30][NMAX+5];
void init(int K, std::vector<int> rr){
n=rr.size();h.resize(n);
k=K;
for(int i=0;i<n;i++)pref[i+1]=pref[i]+rr[i];
for(int e=0;e<3;e++)for(int i=0;i<n;i++){
vec.push_back(rr[i]);
}
//for(auto e:vec)cout<<e<<" ";cout<<"\n";
build(1,0,3*n-1);
int L=0+n+n;int R=n-1+n+n;
step=n;
while(step>=1){
auto[val,pos]=get(1,0,3*n-1,L,R);
extract(pos);
}
for(int i=0;;i++){
if(h.size()==5*n)break;
h.push_back(h[i]);
}
//for(auto e:h)cout<<e<<" ";cout<<"\n";
set<pair<int,int>,greater<pair<int,int>>>st;
int N=5*n;
for(int i=0;i<N;i++){
if(i-1>=0)st.insert({h[i-1],i-1});
if(i-k>=0)st.erase({h[i-k],i-k});
if(st.empty())lefte[0][i]=i;
else if(st.begin()->first>=h[i])lefte[0][i]=i;
else lefte[0][i]=st.begin()->second;
}
st.clear();
for(int i=N-1;i>=0;i--){
if(i+1<N)st.insert({h[i+1],i+1});
if(i+k<N)st.erase({h[i+k],i+k});
if(st.empty())righte[0][i]=i;
else if(st.begin()->first>=h[i])righte[0][i]=i;
else righte[0][i]=st.begin()->second;
}
for(int lvl=1;lvl<30;lvl++){
for(int i=0;i<N;i++){
lefte[lvl][i]=lefte[lvl-1][lefte[lvl-1][i]];
righte[lvl][i]=righte[lvl-1][righte[lvl-1][i]];
}
}
};
int ddist(int u,int v){
return min({abs(u-v),abs(u+n-v),abs(v+n-u)});
}
int lgt(int x,int y){
for(int lvl=29;lvl>=0;lvl--){
int pos=lefte[lvl][x];
if(pos<y)continue;
x=pos;
}
if(ddist(x,y)<k&&h[x]>=h[y])return 1;
return 0;
}
int rgt(int x,int y){
for(int lvl=29;lvl>=0;lvl--){
int pos=righte[lvl][x];
if(pos>y)continue;
x=pos;
}
if(ddist(x,y)<k&&h[x]>=h[y])return 1;
return 0;
}
int gt(int X,int y){
while(X-n>=0)X-=n;
while(y-n>=0)y-=n;
for(int x=X;x<5*n;x+=n){
if(x<y)if(rgt(x,y))return 1;
if(y<x)if(lgt(x,y))return 1;
while(y-n>=0){
y-=n;
if(x<y)if(rgt(x,y))return 1;
if(y<x)if(lgt(x,y))return 1;
}
if(x<y)if(rgt(x,y))return 1;
if(y<x)if(lgt(x,y))return 1;
while(y+n<5*n){
y+=n;
if(x<y)if(rgt(x,y))return 1;
if(y<x)if(lgt(x,y))return 1;
}
}
return 0;
}
int compare_plants(int x, int y){
if(gt(x,y))return 1;
if(gt(y,x))return -1;
return 0;
}
#define MULTITESTS false
void solve(int testCase){
}
// x y
void precalc(){
}
/*
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
precalc();
int t=1;
if(MULTITESTS)cin>>t;
for(int i=1;i<=t;i++){
auto t1=clock();
solve(i);
auto t2=clock();
float delta=t2-t1;
delta/=CLOCKS_PER_SEC;
#ifdef LIS05ST
cout<<"("<<i<<")------------"<<fixed<<setprecision(2)<<delta<<"s\n";
#endif
}
}*/
