//Challenge: Accepted
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
struct segtree {
int seg[4 * maxn], tag[4 * maxn];
void push(int cur, int l, int r) {
if (!tag[cur]) return;
seg[cur] += tag[cur];
if (r - l > 1) {
tag[cur*2] += tag[cur], tag[cur*2+1] += tag[cur];
}
tag[cur] = 0;
}
void pull(int cur, int l, int r) {
if (r - l > 1) {
int m = (l + r) / 2;
push(cur*2, l, m), push(cur*2+1, m, r);
}
seg[cur] = min(seg[cur*2], seg[cur*2+1]);
}
void init(int cur, int l, int r, vector<int> &v) {
if (r <= l) return;
if (r - l == 1) {
seg[cur] = v[l];
return;
}
int m = (l + r) / 2;
init(cur*2, l, m, v);
init(cur*2+1, m, r, v);
pull(cur, l, r);
}
void modify(int cur, int l, int r, int ql, int qr, int v) {
if (r <= l || ql >= r || qr <= l) return;
push(cur, l, r);
if (ql <= l && qr >= r) {
tag[cur] += v;
return;
}
int m = (l + r) / 2;
modify(cur*2, l, m, ql, qr, v), modify(cur*2+1, m, r, ql, qr, v);
pull(cur, l, r);
}
void change(int cur, int l, int r, int ind, int v) {
if (r <= l) return;
push(cur, l, r);
if (r - l == 1) {
seg[cur] = v;
return;
}
int m = (l + r) / 2;
if (ind < m) change(cur*2, l, m, ind, v);
else change(cur*2+1, m, r, ind, v);
pull(cur, l, r);
}
int getleft(int cur, int l, int r) {
if (r <= l) return 0;
push(cur, l, r);
if (r - l == 1) return l;
int m = (l + r) / 2;
push(cur*2, l, m), push(cur*2+1, m, r);
if (seg[cur*2] == 0) return getleft(cur*2, l, m);
else return getleft(cur*2+1, m, r);
}
void getzero(int cur, int l, int r, int ql, int qr, vector<int> &v) { // gets all 0's in range [ql, qr)
if (r <= l || ql >= r || qr <= l) return;
push(cur, l, r);
if (seg[cur] > 0) return;
if (r - l == 1) {
v.push_back(l);
return;
}
int m = (l + r) / 2;
getzero(cur*2, l, m, ql, qr, v);
getzero(cur*2+1, m, r, ql, qr, v);
}
int query(int cur, int l, int r, int ql, int qr) {
if (r <= l || ql >= r || qr <= l) return inf;
if (ql <= l && qr >= r) return seg[cur];
int m = (l + r) / 2;
return min(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr));
}
void print(int cur, int l, int r) {
if (r <= l) return;
push(cur, l, r);
if (r - l == 1) {
debug(seg[cur]);
return;
}
int m = (l + r) / 2;
print(cur*2, l, m), print(cur*2+1, m, r);
}
}tr, aux, to;
int n, k;
int lt[18][maxn], rt[18][maxn], cor[maxn], ord[maxn];
int cl[18][maxn], cr[18][maxn];
void init(int K, vector<int> R) {
n = R.size();
k = K;
tr.init(1, 0, n, R);
aux.init(1, 0, n, R);
auto add = [&] (int i, int d) {
aux.modify(1, 0, n, i+1, min(n, i+k), d);
if (i + k > n) aux.modify(1, 0, n, 0, i + k - n, d);
};
for (int i = 0;i < n;i++) {
to.change(1, 0, n, i, inf);
if (R[i] == 0) add(i, 1);
}
auto getmi = [&] (int l, int r) { //[l, r]
int ret = inf;
if (l < 0) {
ret = min(to.query(1, 0, n, l+n, n), to.query(1, 0, n, 0, r+1));
} else if (r >= n) {
ret = min(to.query(1, 0, n, l, n), to.query(1, 0, n, 0, r - n + 1));
} else {
ret = to.query(1, 0, n, l, r+1);
}
if (ret > maxn) return -1;
return cor[ret];
};
lt[0][n] = rt[0][n] = n;
for (int it = n;it > 0;it--) {
int ind = aux.getleft(1, 0, n);
add(ind, -1);
int lef = getmi(ind-k+1, ind-1), rig = getmi(ind+1, ind+k-1);
cor[it] = ind, ord[ind] = it;
to.change(1, 0, n, ind, it);
if (lef != -1) lt[0][ind] = lef, cl[0][ind] = lef > ind ? 1 : 0;
else lt[0][ind] = n;
if (rig != -1) rt[0][ind] = rig, cr[0][ind] = rig < ind ? 1 : 0;
else rt[0][ind] = n;
vector<int> zero;
tr.change(1, 0, n, ind, inf);
aux.change(1, 0, n, ind, inf);
tr.modify(1, 0, n, max(0, ind-k+1), ind, -1);
aux.modify(1, 0, n, max(0, ind-k+1), ind, -1);
tr.getzero(1, 0, n, max(0, ind-k+1), ind, zero);
if (ind - k + 1 < 0) {
tr.modify(1, 0, n, ind-k+1 + n, n, -1);
aux.modify(1, 0, n, ind-k+1 + n, n, -1);
tr.getzero(1, 0, n, ind-k+1 + n, n, zero);
}
for (auto i:zero) add(i, 1);
}
pary(ord, ord + n);
pary(lt[0], lt[0] + n);
pary(rt[0], rt[0] + n);
for (int i = 1;i < 18;i++) {
for (int j = 0;j <= n;j++) {
lt[i][j] = lt[i-1][lt[i-1][j]];
cl[i][j] = cl[i-1][j] + cl[i-1][lt[i-1][j]];
rt[i][j] = rt[i-1][rt[i-1][j]];
cr[i][j] = cr[i-1][j] + cr[i-1][cr[i-1][j]];
}
}
return;
}
int cdis(int x, int y) {
if (x > y) swap(x, y);
return min(abs(x - y), x + n - y);
}
int compare_plants(int x, int y) {
if (2 * k > n) return (ord[x] < ord[y] ? -1 : 1);
int tx = x, ty = y;
for (int i = 17;i >= 0;i--) {
if (rt[i][tx] != n) assert((rt[i][tx] >= tx) == (cr[i][tx] == 0));
if (rt[i][tx] != n && (rt[i][tx] >= x && rt[i][tx] <= y)) {
tx = rt[i][tx];
}
}
if (cdis(tx, ty) < k && ord[tx] <= ord[ty]) return -1;
tx = x, ty = y;
for (int i = 17;i >= 0;i--) {
if (lt[i][ty] != n && (lt[i][ty] <= y && lt[i][ty] >= x)) {
ty = lt[i][ty];
}
}
if (cdis(tx, ty) < k && ord[tx] >= ord[ty]) return 1;
tx = x, ty = y;
int cnt = 0;
for (int i = 17;i >= 0;i--) {
int nxt = lt[i][tx];
if (nxt != n && ((cl[i][tx] == 1 && !cnt && nxt >= y) || (!cl[i][tx] && (nxt >= y || tx < y)))) {
cnt += cl[i][tx];
tx = nxt;
}
}
if (cdis(tx, ty) < k && ord[tx] <= ord[ty]) return -1;
tx = x, ty = y, cnt = 0;
for (int i = 17;i >= 0;i--) {
int nxt = rt[i][ty];
if (nxt != n && ((cr[i][ty] == 1 && !cnt && nxt <= x) || (!cr[i][ty] && (nxt <= x || ty > x)))) {
cnt += cr[i][ty];
ty = nxt;
}
}
if (cdis(tx, ty) < k && ord[tx] >= ord[ty]) return 1;
return 0;
}
/*
4 3 2
0 1 1 2
0 2
1 2
6 2 5
1 0 1 0 0 0
0 1
3 5
0 3
2 4
2 5
*/
