#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int perm[200010];
queue<int>kolejka;
set<int>zera;
int n, k;
bool dodane[200010];
int nast(int val){
if(zera.size()==0)return -1;
if(zera.upper_bound(val)==zera.end()){
return *zera.begin();
}
return *zera.upper_bound(val);
}
void rozpatrz(int val){
if(val==-1)return;
if(dodane[val])return;
if(zera.lower_bound(val)==zera.begin()){
int pom = *zera.rbegin();
if(val - pom+n > k-1){
kolejka.push(val);
dodane[val] = 1;
}
return;
}
else{
auto it = zera.lower_bound(val);
it--;
int pom =*it;
if(val-pom > k-1){
kolejka.push(val);
dodane[val] = 1;
}
}
}
const int base = 1<<18;
int mini[2*base];
int lazy[2*base];
void push(int w){
if(!lazy[w])return;
mini[w*2]+=lazy[w];
lazy[w*2]+=lazy[w];
mini[w*2+1]+=lazy[w];
lazy[w*2+1]+=lazy[w];
mini[w] = min(mini[w*2], mini[w*2+1]);
lazy[w] = 0;
}
void dodaj(int w, int l, int p, int a, int b, int val){
if(b<l || p<a)return;
if(a<=l && p<=b){
mini[w]+=val;
lazy[w]+=val;
return;
}
push(w);
dodaj(w*2, l, (l+p)/2, a, b, val);
dodaj(w*2+1, (l+p)/2+1, p, a, b, val);
mini[w] = min(mini[w*2], mini[w*2+1]);
}
void odejmij(int l, int p){
l = (l+n)%n, p = (p+n)%n;
if(l<=p)
dodaj(1, 0, base-1, l, p, -1);
else{
dodaj(1, 0, base-1, l, n-1, -1);
dodaj(1, 0, base-1, 0, p, -1);
}
}
int znajdz(int w){
if(w>base){
if(mini[w]==0)return w-base;
else return -1;
}
if(mini[w]>0)return -1;
push(w);
int pom = znajdz(w*2);
if(pom==-1)pom = znajdz(w*2+1);
else znajdz(w*2+1);
mini[w] = min(mini[w*2], mini[w*2+1]);
return pom;
}
void init(int K, std::vector<int> r) {
n = r.size();
int i;
k = K;
//odzyskaj permutacje
for(i=0;i<n;i++)
if(r[i]==0)
zera.insert(i);
for(auto j: zera){
rozpatrz(j);
}
for(i=0;i<base;i++){
if(i>n || r[i]==0)
dodaj(1, 0, base-1, i, i, 1000000000);
else
dodaj(1, 0, base-1, i, i, r[i]);
}
int numer = n-1;
while(kolejka.size()){
auto x = kolejka.front();
kolejka.pop();
perm[x] = numer--;
zera.erase(x);
odejmij(x-k+1, x-1);
vector<int>nowe_zera;
while(mini[1]==0){
int j = znajdz(1);
dodaj(1, 0, base-1, j, j, 1000000000);
zera.insert(j);
nowe_zera.push_back(j);
}
for(auto j: nowe_zera)
rozpatrz(j);
rozpatrz(nast(x));
// for(auto j: nowe_zera)printf("%d ", j);
// printf("\nKONIEC %d\n", x);
}
// for(i=0;i<n;i++)printf("%d ", perm[i]);printf("\n");
return;
}
int compare_plants(int x, int y) {
if(perm[x]<perm[y]) return -1;
if(perm[x]>perm[y]) return 1;
return 0;
}
