#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct T{
int mn,pos;
}st[800001];
T operator +(T a, T b){
return (a.mn>b.mn?b:a);
}
int n,k,lazy[800001],p[200001],id;
vector <int> a;
void down(int node, int l, int r){
if (!lazy[node]||l==r)
return;
st[node<<1].mn+=lazy[node];
st[node<<1|1].mn+=lazy[node];
lazy[node<<1]+=lazy[node];
lazy[node<<1|1]+=lazy[node];
lazy[node]=0;
}
void build(int node, int l, int r){
if (l==r){
st[node]={a[l],l};
return;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
st[node]=st[node<<1]+st[node<<1|1];
}
void update(int node, int l, int r, int u, int v, int val){
if (l>v||r<u||u>v)
return;
if (l>=u&&r<=v){
st[node].mn+=val;
lazy[node]+=val;
return;
}
down(node,l,r);
int mid=(l+r)>>1;
update(node<<1,l,mid,u,v,val);
update(node<<1|1,mid+1,r,u,v,val);
st[node]=st[node<<1]+st[node<<1|1];
}
T get(int node, int l, int r, int u, int v){
if (l>v||r<u||u>v)
return {INF,0};
if (l>=u&&r<=v)
return st[node];
down(node,l,r);
int mid=(l+r)>>1;
return get(node<<1,l,mid,u,v)+get(node<<1|1,mid+1,r,u,v);
}
int calc(int j){
T t={INF,0};
if (j<k)
t=get(1,0,n-1,0,j-1)+get(1,0,n-1,n+j-k+1,n-1);
else
t=get(1,0,n-1,j-k+1,j-1);
if (t.mn)
return -1;
return t.pos;
}
void dfs(int i){
while (calc(i)!=-1)
dfs(calc(i));
p[i]=id;
id--;
if (i<k){
update(1,0,n-1,0,i-1,-1);
update(1,0,n-1,n+i-k+1,n-1,-1);
}
else
update(1,0,n-1,i-k+1,i-1,-1);
update(1,0,n-1,i,i,INF);
}
void init(int K, vector <int> r){
k=K;
a=r;
n=id=a.size();
build(1,0,n-1);
while (!st[1].mn)
dfs(st[1].pos);
}
int compare_plants(int x, int y){
return (p[x]>p[y]?1:(p[x]<p[y]?-1:0));
}
