#include "plants.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
const int MAXN = 2e5+1, base = (1<<18);
int n, k, when[MAXN], nr;
int ptr[MAXN], ptrr[MAXN];
vector<int> R;
pii tree_max[2*base+1];
void upd(int x) {
pii val = mp(when[x], x);
x+=base;
while(x) {
tree_max[x] = max(tree_max[x], val);
x/=2;
}
}
pii find_max(int l, int r) {
if(l>r) {
return max(find_max(l, n-1), find_max(0, r));
}
l+=base, r+=base;
pii res = tree_max[l];
if(l!=r) res = max(res, tree_max[r]);
while(l/2 != r/2) {
if(l%2==0) res = max(res, tree_max[l+1]);
if(r%2==1) res = max(res, tree_max[r-1]);
l /= 2;
r /= 2;
}
return res;
}
int tree[2*base+1], push[2*base+1];
void ADD(int id, int val) {
tree[id] += val;
push[id] += val;
}
void add(int l, int r, int val, int id=1, int rl=0, int rr=base-1) {
if(l>r) {
add(l, n-1, val), add(0, r, val);
return;
}
if(l>rr || r<rl) return;
if(l<=rl && r>=rr) {
ADD(id, val);
return;
}
ADD(id*2, push[id]), ADD(id*2+1, push[id]);
push[id] = 0;
add(l, r, val, id*2, rl, (rl+rr)/2), add(l, r, val, id*2+1, (rl+rr)/2+1, rr);
tree[id] = min(tree[id*2], tree[id*2+1]);
}
int find_closest_zero(int l, int r, int id=1, int rl=0, int rr=base-1) {
if(l>rr || r<rl || tree[id]>0) return -1;
if(rl==rr) {
return rl;
}
ADD(id*2, push[id]), ADD(id*2+1, push[id]);
push[id] = 0;
int rs = find_closest_zero(l, r, id*2+1, (rl+rr)/2+1, rr);
if(rs!=-1) return rs;
return find_closest_zero(l, r, id*2, rl, (rl+rr)/2);
}
int clw_dist(int x, int y) {
return (x<=y)? y-x: n-(x-y);
}
void solve(int x) {
//cerr<<"solve("<<x<<")\n";
while(true) {
int prv = -1;
if(x>0) {
prv = find_closest_zero(0, x-1);
}
if(x<n-1 && prv==-1) {
prv = find_closest_zero(x+1, n-1);
}
if(prv != -1 && clw_dist(prv, x) < k) {
//cerr<<"->";
solve(prv);
}
else {
break;
}
}
when[x] = ++nr;
ptr[x] = find_max((x+1)%n, (x+k-1)%n).second;
ptrr[x] = find_max((x-(k-1)+n)%n, (x-1+n)%n).second;
add((x-(k-1)+n)%n, (x-1+n)%n, -1);
add(x, x, n);
upd(x);
}
void prep_jumps();
void init(int _k, vector<int> _r) {
k = _k, R = _r, n = R.size();
for(int i=0; i<2*base; ++i) {
tree_max[i] = mp(-1, -1);
}
for(int i=0; i<n; ++i) {
tree[i+base] = R[i];
}
for(int i=base-1; i>=1; --i) {
tree[i] = min(tree[i*2], tree[i*2+1]);
}
while(nr < n) {
int cur = find_closest_zero(0, n-1);
assert(cur != -1);
solve(cur);
}
prep_jumps();
}
const int L = 19;
pii jump[L][MAXN], jumpr[L][MAXN];
void prep_jumps() {
for(int i=0; i<n; ++i) {
jump[0][i] = mp(ptr[i], clw_dist(i, ptr[i]));
jumpr[0][i] = mp(ptrr[i], clw_dist(ptrr[i], i));
}
for(int l=1; l<L; ++l) {
for(int i=0; i<n; ++i) {
if(jump[l-1][i].st != -1) {
jump[l][i] = jump[l-1][jump[l-1][i].st];
jump[l][i].nd += jump[l-1][i].nd;
jump[l][i].nd = min(n, jump[l][i].nd);
}
else {
jump[l][i] = mp(-1, 1);
}
if(jumpr[l-1][i].st != -1) {
jumpr[l][i] = jumpr[l-1][jumpr[l-1][i].st];
jumpr[l][i].nd += jumpr[l-1][i].nd;
jumpr[l][i].nd = min(n, jumpr[l][i].nd);
}
else {
jumpr[l][i] = mp(-1, 1);
}
}
}
}
bool is_bigger(int _x, int y) {
int x = _x;
for(int l=L-1; l>=0; --l) {
if(jump[l][x].st!=-1 && jump[l][x].nd <= clw_dist(x, y)) {
x = jump[l][x].st;
}
}
if(clw_dist(x, y)<k && when[x] >= when[y]) return true;
x = _x;
for(int l=L-1; l>=0; --l) {
if(jumpr[l][x].st!=-1 && jumpr[l][x].nd <= clw_dist(y, x)) {
x = jumpr[l][x].st;
}
}
if(clw_dist(y, x)<k && when[x] >= when[y]) return true;
return false;
}
int compare_plants(int x, int y) {
if(is_bigger(x, y)) return -1;
if(is_bigger(y, x)) return 1;
return 0;
}
