#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, INF=1e9+7;
set<int>A, B;
pair<int,int>tr[4*LIM];
int lazy[4*LIM], T[LIM], n, k, N=1;
void spl(int v) {
tr[2*v].st+=lazy[v];
tr[2*v+1].st+=lazy[v];
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
if(r<a || b<l) return;
if(a<=l && r<=b) {
tr[v].st+=x;
lazy[v]+=x;
return;
}
if(lazy[v]) spl(v);
int mid=(l+r)/2;
upd(2*v, l, mid, a, b, x);
upd(2*v+1, mid+1, r, a, b, x);
tr[v]=min(tr[2*v], tr[2*v+1]);
}
pair<int,int>cnt(int v, int l, int r, int a, int b) {
if(r<a || b<l) return {INF, INF};
if(a<=l && r<=b) return tr[v];
if(lazy[v]) spl(v);
int mid=(l+r)/2;
return min(cnt(2*v, l, mid, a, b), cnt(2*v+1, mid+1, r, a, b));
}
int dyst(int a, int b) {
if(a<b) return b-a;
return n-a+b;
}
pair<int,int>licz(int x) {
auto it=A.lower_bound(x);
int a=-1, b=-1;
if(it==A.end()) {
auto it2=A.begin();
b=*it2;
} else b=*it;
if(it==A.begin()) {
auto it2=A.end(); --it2;
a=*it2;
} else {
--it;
a=*it;
}
return {a, b};
}
void dodaj(int x) {
if(A.size()==0) {
A.insert(x);
B.insert(x);
return;
}
pair<int,int>p=licz(x);
int a=p.st, b=p.nd;
if(dyst(x, b)<k && B.find(b)!=B.end()) B.erase(b);
if(dyst(a, x)>=k) B.insert(x);
A.insert(x);
}
void usun(int x) {
A.erase(x);
if(B.find(x)!=B.end()) B.erase(x);
if(A.size()==1) B.insert(*A.begin());
if(A.size()<2) return;
pair<int,int>p=licz(x);
int a=p.st, b=p.nd;
if(dyst(a, b)>=k) B.insert(b);
}
void init(int _k, vector<int>r) {
n=r.size(); k=_k;
while(N<n) N*=2;
rep(i, n) tr[N+i]={r[i], i};
for(int i=n; i<N; ++i) tr[N+i]={INF, INF};
for(int i=N-1; i; --i) tr[i]=min(tr[2*i], tr[2*i+1]);
rep(i, n) {
while(tr[1].st==0) {
dodaj(tr[1].nd);
upd(1, 0, N-1, tr[1].nd, tr[1].nd, INF);
}
int x=*B.begin();
usun(x);
upd(1, 0, N-1, x-k+1, x, -1);
if(x-k+1<0) upd(1, 0, N-1, n+x-k+1, n-1, -1);
T[x]=n-i;
}
}
int compare_plants(int x, int y) {
if(T[x]>T[y]) return 1;
return -1;
}
