#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
int n, k;
constexpr int R = 1 << 18;
int blocked[R * 2];
pair<int, int> mn[R * 2];
pair<int, int> mn_free[R * 2];
int add[R * 2];
void build() {
for (int i = 0; i < R; ++i) {
mn[i + R] = mn_free[i + R] = make_pair(0, i);
}
for (int i = R - 1; i > 0; --i) {
mn[i] = mn_free[i] = min(mn[i * 2], mn[i * 2 + 1]);
}
}
void push(int node) {
if (add[node] != 0) {
mn[node * 2].first += add[node];
mn_free[node * 2].first += add[node];
add[node * 2] += add[node];
mn[node * 2 + 1].first += add[node];
mn_free[node * 2 + 1].first += add[node];
add[node * 2 + 1] += add[node];
}
add[node] = 0;
}
void add_blocked(int ql, int qr, int val, int node = 1, int nl = 0, int nr = R) {
if (ql <= nl && nr <= qr) {
blocked[node] += val;
if (blocked[node] == 0) {
if (nl == nr - 1) {
mn_free[node] = mn[node];
} else {
push(node);
mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
mn_free[node] = min(mn_free[node * 2], mn_free[node * 2 + 1]);
}
} else {
mn_free[node] = make_pair(R, -1);
}
return;
}
if (qr <= nl || nr <= ql) {
return;
}
push(node);
int nm = (nl + nr) / 2;
add_blocked(ql, qr, val, node * 2, nl, nm);
add_blocked(ql, qr, val, node * 2 + 1, nm, nr);
mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
if (blocked[node] == 0) {
mn_free[node] = min(mn_free[node * 2], mn_free[node * 2 + 1]);
}
}
void add_val(int ql, int qr, int val, int node = 1, int nl = 0, int nr = R) {
if (ql <= nl && nr <= qr) {
mn[node].first += val;
mn_free[node].first += val;
add[node] += val;
return;
}
if (qr <= nl || nr <= ql) {
return;
}
push(node);
int nm = (nl + nr) / 2;
add_val(ql, qr, val, node * 2, nl, nm);
add_val(ql, qr, val, node * 2 + 1, nm, nr);
mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
if (blocked[node] == 0) {
mn_free[node] = min(mn_free[node * 2], mn_free[node * 2 + 1]);
}
}
int get_free_zero(int node = 1, int nl = 0, int nr = R) {
if (blocked[node]) {
return -1;
}
// cout << nl << ' ' << nr << ' ' << mn[node].first << endl;
if (mn_free[node].first != 0) {
return -1;
}
if (nl == nr - 1) {
return mn[node].second;
}
push(node);
int nm = (nl + nr) / 2;
int ans = get_free_zero(node * 2, nl, nm);
if (ans == -1) {
ans = get_free_zero(node * 2 + 1, nm, nr);
}
mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
mn_free[node] = min(mn_free[node * 2], mn_free[node * 2 + 1]);
return ans;
}
void get_all_zero(int ql, int qr, vector<int> &ans, int node = 1, int nl = 0, int nr = R) {
if (mn[node].first != 0) {
return;
}
if (qr <= nl || nr <= ql) {
return;
}
if (nl == nr - 1) {
ans.push_back(mn[node].second);
return;
}
push(node);
int nm = (nl + nr) / 2;
get_all_zero(ql, qr, ans, node * 2, nl, nm);
get_all_zero(ql, qr, ans, node * 2 + 1, nm, nr);
mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
if (blocked[node] == 0) {
mn_free[node] = min(mn_free[node * 2], mn_free[node * 2 + 1]);
}
}
constexpr int R2 = 1 << 20;
int mx[R2 * 2];
void build_mx() {
for (int i = 1; i < R2 * 2; ++i) {
mx[i] = -1;
}
}
void _change(int pos, int val) {
for (pos += R2; pos > 0; pos /= 2) {
mx[pos] = max(mx[pos], val);
}
}
void change(int pos, int val) {
_change(pos, val);
_change(pos + n, val);
_change(pos + n * 2, val);
}
int _get(int l, int r) {
l = max(0, l);
r = min(R2, r);
l += R2;
r += R2;
int ans = -1;
while (l < r) {
if (l & 1) {
ans = max(ans, mx[l++]);
}
if (r & 1) {
ans = max(ans, mx[--r]);
}
l >>= 1;
r >>= 1;
}
return ans;
}
int get(int l, int r) {
return _get(l + n, r + n);
}
constexpr int maxn = 2e5 + 5, lg = 20;
vector<int> ord;
int pos[maxn];
pair<pair<int, int>, int> go_left[lg][maxn][2], go_right[lg][maxn][2];
int prv_left[maxn][2], prv_right[maxn][2];
void init(int _k, vector<int> r) {
n = r.size();
k = _k;
build();
add_blocked(n, R, 1);
for (int i = 0; i < n; ++i) {
if (r[i] == 0) {
if (i + k <= n) {
add_blocked(i + 1, i + k, 1);
} else {
add_blocked(i + 1, n, 1);
add_blocked(0, (i + k) % n, 1);
}
}
add_val(i, i + 1, r[i]);
}
for (int _ = 0; _ < n; ++_) {
int pos_mx = get_free_zero();
// cout << pos_mx << endl;
ord.push_back(pos_mx);
vector<int> new_zero;
if (pos_mx >= k - 1) {
add_val(pos_mx - k + 1, pos_mx, -1);
get_all_zero(pos_mx - k + 1, pos_mx, new_zero);
} else {
if (pos_mx > 0) {
add_val(0, pos_mx, -1);
get_all_zero(0, pos_mx, new_zero);
}
add_val(n - (k - pos_mx) + 1, n, -1);
get_all_zero(n - (k - pos_mx) + 1, n, new_zero);
}
if (pos_mx + k <= n) {
add_blocked(pos_mx + 1, pos_mx + k, -1);
} else {
add_blocked(pos_mx + 1, n, -1);
add_blocked(0, (pos_mx + k) % n, -1);
}
add_val(pos_mx, pos_mx + 1, R);
// cout << pos_mx << ' ' << new_zero.size() << endl;
for (auto pos : new_zero) {
if (pos + k <= n) {
add_blocked(pos + 1, pos + k, 1);
} else {
add_blocked(pos + 1, n, 1);
add_blocked(0, (pos + k) % n, 1);
}
}
}
reverse(ord.begin(), ord.end());
build_mx();
for (int i = 0; i < n; ++i) {
prv_left[i][0] = get(ord[i] - k + 1, ord[i]);
prv_left[i][1] = get(ord[i] - k + 1 - n, ord[i] - n);
prv_right[i][0] = get(ord[i] + 1, ord[i] + k);
prv_right[i][1] = get(ord[i] + 1 + n, ord[i] + k + n);
change(ord[i], i);
if (prv_left[i][0] != -1) {
if (ord[i] - k < ord[prv_left[i][0]] && ord[prv_left[i][0]] < ord[i]) {
go_left[0][i][0] = make_pair(make_pair(prv_left[i][0], 0), ord[prv_left[i][0]] - k);
} else {
go_left[0][i][0] = make_pair(make_pair(prv_left[i][0], 1), ord[prv_left[i][0]] - k - n);
}
} else {
go_left[0][i][0] = make_pair(make_pair(-1, -1), R);
}
if (prv_left[i][1] != -1) {
go_left[0][i][1] = make_pair(make_pair(prv_left[i][1], 1), ord[prv_left[i][1]] - k - n);
} else {
go_left[0][i][1] = make_pair(make_pair(-1, -1), R);
}
if (prv_right[i][0] != -1) {
if (ord[i] < ord[prv_right[i][0]] && ord[prv_right[i][0]] < ord[i] + k) {
go_right[0][i][0] = make_pair(make_pair(prv_right[i][0], 0), ord[prv_right[i][0]] + k);
} else {
go_right[0][i][0] = make_pair(make_pair(prv_right[i][0], 1), ord[prv_right[i][0]] + k + n);
}
} else {
go_right[0][i][0] = make_pair(make_pair(-1, -1), -R);
}
if (prv_right[i][1] != -1) {
go_right[0][i][1] = make_pair(make_pair(prv_right[i][1], 1), ord[prv_right[i][1]] + k + n);
} else {
go_right[0][i][1] = make_pair(make_pair(-1, -1), -R);
}
}
for (int i = 1; i < lg; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < 2; ++k) {
if (go_left[i - 1][j][k].first.first != -1 && go_left[i - 1][go_left[i - 1][j][k].first.first][go_left[i - 1][j][k].first.second].first.first != -1) {
go_left[i][j][k].first.first = go_left[i - 1][go_left[i - 1][j][k].first.first][go_left[i - 1][j][k].first.second].first.first;
go_left[i][j][k].first.second = go_left[i - 1][go_left[i - 1][j][k].first.first][go_left[i - 1][j][k].first.second].first.second;
go_left[i][j][k].second = min(go_left[i - 1][j][k].second, go_left[i - 1][go_left[i - 1][j][k].first.first][go_left[i - 1][j][k].first.second].second);
} else {
go_left[i][j][k] = make_pair(make_pair(-1, -1), R);
}
if (go_right[i - 1][j][k].first.first != -1 && go_right[i - 1][go_right[i - 1][j][k].first.first][go_right[i - 1][j][k].first.second].first.first != -1) {
go_right[i][j][k].first.first = go_right[i - 1][go_right[i - 1][j][k].first.first][go_right[i - 1][j][k].first.second].first.first;
go_right[i][j][k].first.second = go_right[i - 1][go_right[i - 1][j][k].first.first][go_right[i - 1][j][k].first.second].first.second;
go_right[i][j][k].second = max(go_right[i - 1][j][k].second, go_right[i - 1][go_right[i - 1][j][k].first.first][go_right[i - 1][j][k].first.second].second);
} else {
go_right[i][j][k] = make_pair(make_pair(-1, -1), -R);
}
}
}
}
for (int i = 0; i < n; ++i) {
pos[ord[i]] = i;
}
}
int compare_plants(int x, int y) {
if (pos[x] > pos[y]) {
int l = x - k, r = x + k;
int nw1 = pos[x], nw2 = 0;
for (int i = lg - 1; i >= 0; --i) {
if (go_left[i][nw1][nw2].first.first > pos[y]) {
l = min(l, go_left[i][nw1][nw2].second);
int nw3 = go_left[i][nw1][nw2].first.first, nw4 = go_left[i][nw1][nw2].first.second;
nw1 = nw3, nw2 = nw4;
}
}
nw1 = pos[x], nw2 = 0;
for (int i = lg - 1; i >= 0; --i) {
if (go_right[i][nw1][nw2].first.first > pos[y]) {
r = max(r, go_right[i][nw1][nw2].second);
int nw3 = go_right[i][nw1][nw2].first.first, nw4 = go_right[i][nw1][nw2].first.second;
nw1 = nw3, nw2 = nw4;
}
}
if ((l < y && y < r) || (l < y - n && y - n < r) || (l < y + n && y + n < r)) {
return 1;
}
return 0;
} else {
swap(x, y);
int l = x - k, r = x + k;
int nw1 = pos[x], nw2 = 0;
for (int i = lg - 1; i >= 0; --i) {
if (go_left[i][nw1][nw2].first.first > pos[y]) {
l = min(l, go_left[i][nw1][nw2].second);
int nw3 = go_left[i][nw1][nw2].first.first, nw4 = go_left[i][nw1][nw2].first.second;
nw1 = nw3, nw2 = nw4;
}
}
nw1 = pos[x], nw2 = 0;
for (int i = lg - 1; i >= 0; --i) {
if (go_right[i][nw1][nw2].first.first > pos[y]) {
r = max(r, go_right[i][nw1][nw2].second);
int nw3 = go_right[i][nw1][nw2].first.first, nw4 = go_right[i][nw1][nw2].first.second;
nw1 = nw3, nw2 = nw4;
}
}
if ((l < y && y < r) || (l < y - n && y - n < r) || (l < y + n && y + n < r)) {
return -1;
}
return 0;
}
}
