#include<bits/stdc++.h>
#include "plants.h"
using namespace std;
const int N = 200010;
int v[N];
int n;
int ans[N];
struct Segtree{
int tree[4*N], lazy[4*N];
int join(int a, int b){
return min(a, b);
}
void build(int node, int l, int r){
lazy[node] = 0;
if(l == r){
tree[node] = v[l];
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
void unlazy(int node, int l, int r){
tree[node] += lazy[node];
if(l != r){
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
void update(int node, int l, int r, int tl, int tr, int val){
unlazy(node, tl, tr);
if(l > tr or tl > r) return;
if(l <= tl and tr <= r){
lazy[node] += val;
unlazy(node, tl, tr);
return;
}
int mid = (tl+tr)/2;
update(2*node, l, r, tl, mid, val);
update(2*node+1, l, r, mid+1, tr, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
int query(int node, int l, int r, int tl, int tr){
unlazy(node, tl, tr);
if(l > tr or tl > r) return 1e8;
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
int busca(int node, int l, int r, int tl, int tr, int val){
unlazy(node, tl, tr);
if(l > tr or tl > r) return 1e8;
if(l <= tl and tr <= r){
if(tree[node] > val) return 1e8;
if(tl == tr) return tl;
int mid = (tl+tr)/2;
unlazy(2*node, tl, mid);
unlazy(2*node+1, mid+1, tr);
if(tree[2*node] <= val) return busca(2*node, l, r, tl, mid, val);
else return busca(2*node+1, l, r, mid+1, tr, val);
}
int mid = (tl+tr)/2;
int d = busca(2*node, l, r, tl, mid, val);
if(d != 1e8) return d;
return busca(2*node+1, l, r, mid+1, tr, val);
}
} seg;
int k;
int ask(int l, int r){
if(l <= r) return seg.query(1, l, r, 0, n-1);
return min(seg.query(1, l, n-1, 0, n-1), seg.query(1, 0, r, 0, n-1));
}
bool incluso(int x, int l, int r){
if(l <= r){
if(l <= x and x <= r) return true;
return false;
}
else{
if(l <= x and x <= n-1) return true;
if(0 <= x and x <= r) return true;
return false;
}
}
struct Plants{
set <int> idx;
int answer;
void build(){
int l = 0, r = n-1;
while(l <= r){
int d = seg.busca(1, l, r, 0, n-1, 0);
if(d == 1e8) break;
idx.insert(d);
l = d+1;
}
for(auto x : idx){
if(ask(((x-k+1)+n)%n, x-1) != 0) answer = x;
}
}
void run(int tt){
ans[answer] = tt;
idx.erase(answer);
seg.update(1, answer, answer, 0, n-1, 1e8);
int r = answer, l = answer-k+1;
if(l < 0) l += n;
if(l <= r){
seg.update(1, l, r, 0, n-1, -1);
vector <int> add;
while(l <= r){
int d = seg.busca(1, l, r, 0, n-1, 0);
if(d == 1e8) break;
add.push_back(d);
l = d+1;
}
if(add.empty()){
if(idx.empty()) return;
else if(idx.size() == 1){
answer = *(idx.begin());
}
else{
auto it = idx.upper_bound(answer);
if(it == idx.end()) it = idx.begin();
answer = *it;
}
}
else{
if(idx.empty()){
answer = add[0];
for(auto x : add) idx.insert(x);
}
else{
auto it = idx.upper_bound(add.back());
if(it == idx.end()) it = idx.begin();
int valor = *it;
if(incluso(add.back(), (valor-(k-1)+n)%n, valor)){
answer = add[0];
}
else{
answer = valor;
}
for(auto x : add){
idx.insert(x);
}
}
}
}
else{
seg.update(1, l, n-1, 0, n-1, -1);
seg.update(1, 0, r, 0, n-1, -1);
vector <int> add;
while(l <= n-1){
int d = seg.busca(1, l, n-1, 0, n-1, 0);
if(d == 1e8) break;
add.push_back(d);
l = d+1;
}
l = 0;
while(l <= r){
int d = seg.busca(1, l, n-1, 0, n-1, 0);
if(d == 1e8) break;
add.push_back(d);
l = d+1;
}
if(add.empty()){
if(idx.empty()) return;
else if(idx.size() == 1){
answer = *(idx.begin());
}
else{
auto it = idx.upper_bound(answer);
if(it == idx.end()) it = idx.begin();
answer = *it;
}
}
else{
if(idx.empty()){
answer = add[0];
for(auto x : add) idx.insert(x);
}
else{
auto it = idx.upper_bound(add.back());
if(it == idx.end()) it = idx.begin();
int valor = *it;
if(incluso(add.back(), (valor-(k-1)+n)%n, valor)){
answer = add[0];
}
else{
answer = valor;
}
for(auto x : add){
idx.insert(x);
}
}
}
}
}
} plants;
void init(int kk, std::vector<int> r) {
k = kk;
n = r.size();
for(int i = 0; i < r.size();i++){
v[i] = r[i];
}
seg.build(1, 0, n-1);
plants.build();
for(int tt = n-1;tt >= 0;tt--){
plants.run(tt);
}
for(int i = 0;i < n;i++){
// cout << ans[i] << ' ';
}
return;
}
int compare_plants(int x, int y) {
if(ans[x] > ans[y]) return 1;
return -1;
return 0;
}
