#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define X first
#define Y second
#define lc id << 1
#define rc lc | 1
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
int n , k , ans = -1 , A[MAXN] , val[MAXN] , lz[MAXN << 2];
pii seg[MAXN << 2];
set<int> st;
void Insert(int x){
int y = (*prev(st.lower_bound(x)));
if(x - y >= k) ans = x;
st.insert(x);
}
void build(int id = 1 , int l = 0 , int r = n){
if(r - l == 1){
seg[id] = {A[l] , l};
return;
}
int mid = l + r >> 1;
build(lc , l , mid);
build(rc , mid , r);
seg[id] = min(seg[lc] , seg[rc]);
}
void shift(int id){
lz[lc] += lz[id]; seg[lc].X += lz[id];
lz[rc] += lz[id]; seg[rc].X += lz[id];
lz[id] = 0;
}
void add(int ql , int qr , int val , int id = 1 , int l = 0 , int r = n){
if(qr <= l || r <= ql) return;
if(ql <= l && r <= qr && (seg[id].X + val > 0 || r - l == 1)){
lz[id] += val;
seg[id].X += val;
if(seg[id].X == 0) Insert(l);
return;
}
shift(id);
int mid = l + r >> 1;
add(ql , qr , val , lc , l , mid);
add(ql , qr , val , rc , mid , r);
seg[id] = min(seg[lc] , seg[rc]);
}
pii get(int ql , int qr , int id = 1 , int l = 0 , int r = n){
if(qr <= l || r <= ql) return {MOD , MOD};
if(ql <= l && r <= qr) return seg[id];
shift(id);
int mid = l + r >> 1;
return min(get(ql , qr , lc , l , mid) , get(ql , qr , rc , mid , r));
}
void Add(int l , int r , int val){
if(l < r){
add(l , r , val);
return;
}
add(0 , r , val); add(l , n , val);
return;
}
pii Get(int l , int r){
if(l < r) return get(l , r);
pii A = get(0 , r) , B = get(l , n);
if(A.X < B.X) return A;
return B;
}
void init(int K, vector<int> r) {
k = K; n = r.size();
for(int i = 0 ; i < n ; i++) A[i] = r[i];
build(); st.insert(-1);
for(int i = 0 ; i < n ; i++){
if(A[i] == 0){
Insert(i);
}
}
for(int i = 0 ; i < n ; i++){
int pos = ans;
if(pos == -1) pos = (*st.lower_bound(0));
st.erase(pos);
if(st.lower_bound(pos) != st.end()){
ans = (*st.lower_bound(pos));
if(ans < k - 1) ans = -1;
}
else ans = -1;
Add((pos + n - k + 1) % n , pos , -1);
Add(pos , pos + 1 , MOD);
val[pos] = n - i;
}
return;
}
int compare_plants(int x, int y) {
if(val[x] < val[y]) return -1;
if(val[x] > val[y]) return 1;
return 0;
}
