#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)2e5 + 100;
int A[N];
int vl[N];
struct Node{
pii valid; // = r + vl
pii zero; // = r
int rlazy;
int vllazy;
};
Node T[N * 4 + 512];
void push(int node, int cl, int cr){
T[node].valid.fi += T[node].rlazy + T[node].vllazy;
T[node].zero.fi += T[node].rlazy;
if(cl != cr){
T[node*2].rlazy += T[node].rlazy;
T[node*2+1].rlazy += T[node].rlazy;
T[node*2].vllazy += T[node].vllazy;
T[node*2+1].vllazy += T[node].vllazy;
}
T[node].rlazy = 0;
T[node].vllazy = 0;
}
void upd(int node, int cl, int cr, int tl, int tr, int typ, int v){
push(node, cl, cr);
if(cr < tl || cl > tr)
return;
if(cl >= tl && cr <= tr){
if(typ == 0) T[node].rlazy = v;
else T[node].vllazy = v;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
upd(node * 2, cl, mid, tl, tr, typ, v);
upd(node * 2 + 1, mid + 1, cr, tl, tr, typ, v);
T[node].valid = min(T[node*2].valid, T[node*2+1].valid);
T[node].zero = min(T[node*2].zero, T[node*2+1].zero);
}
pii get(int node, int cl, int cr, int tl, int tr, int ta){
push(node, cl, cr);
if(cr < tl || cl > tr)
return mp((int)1e9, (int)1e9);
if(cl >= tl && cr <= tr){
if(ta == 0)
return T[node].zero;
else
return T[node].valid;
}
int mid = (cl + cr) / 2;
return min(get(node * 2, cl, mid, tl, tr, ta), get(node * 2 + 1, mid + 1, cr, tl, tr, ta));
}
vector<int> r;
void build(int node, int cl, int cr){
if(cl == cr){
T[node].valid = mp(r[cl], cl);
T[node].zero = mp(r[cl], cl);
return;
}
int mid = (cl + cr) / 2;
build(node * 2, cl, mid);
build(node * 2 + 1, mid + 1, cr);
T[node].valid = min(T[node * 2].valid, T[node * 2 + 1].valid);
T[node].zero = min(T[node * 2].zero, T[node * 2 + 1].zero);
}
int n, k;
void upd_zero(int ii, int sign){
int nx = (ii + k - 1) % n;
if(nx > ii){
upd(1, 0, n - 1, ii + 1, nx, 1, sign);
}
else{
upd(1, 0, n - 1, ii + 1, n - 1, 1, sign);
upd(1, 0, n - 1, 0, nx, 1, sign);
}
}
vector<int> getz(int li, int ri){
vector<int> soln;
pii cc;
while(li <= ri){
cc = get(1, 0, n - 1, li, ri, 0);
if(cc.fi != 0) return soln;
soln.push_back(cc.se);
li = cc.se + 1;
}
return soln;
}
void init(int k_, vector<int> r_) {
r = r_;
k = k_;
n = r.size();
build(1, 0, n - 1);
for(int i = 0 ; i < n; i ++ ){
if(r[i] == 0){
upd_zero(i,+1);
}
}
int st;
int pv;
int nx;
for(int id = n - 1; id >= 0 ; id -- ){
st = T[1].valid.se;
A[st] = id;
pv = (st - (k - 1) + n) % n;
upd(1, 0, n - 1, st, st, 0, (int)1e9);
upd_zero(st,-1);
vector<int> nwz, cc;
if(pv < st){
upd(1, 0, n - 1, pv, st - 1, 0, -1);
cc = getz(pv, st - 1);
for(auto q : cc) nwz.push_back(q);
}
else{
upd(1, 0, n - 1, 0, st - 1, 0, -1);
upd(1, 0, n - 1, pv, n - 1, 0, -1);
cc = getz(0, st - 1);
for(auto q : cc) nwz.push_back(q);
cc = getz(pv, n - 1);
for(auto q : cc) nwz.push_back(q);
}
for(auto x : nwz){
upd_zero(x,+1);
}
}
}
int compare_plants(int x, int y) {
if(A[x] < A[y]) return -1;
return +1;
}
