#include "plants.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
#define sz(x) ((int)(x).size())
int K, N;
const int nmax = 2e5 + 5;
template<typename T>
struct AINT {
vector<T> aint;
int n;
void init(int n_) {
n = n_;
aint.assign(2 * n + 5, T());
}
template<int dir = 0, class CB> void walk(CB&& cb) { walk<dir>(cb, 0, n - 1); }
template<int dir = 0, class CB> void walk(CB&& cb, int l, int r) { walk<dir>(cb, l, r, 1, 0, n - 1); }
template<int dir = 0, class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) {
if(cr < l || r < cl) return;
if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return;
int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
aint[node].push(aint[L], aint[R]);
if(dir == 0) { walk<dir>(cb, l, r, L, cl, mid); walk<dir>(cb, l, r, R, mid + 1, cr); }
if(dir == 1) { walk<dir>(cb, l, r, R, mid + 1, cr); walk<dir>(cb, l, r, L, cl, mid); }
aint[node].pull(aint[L], aint[R]);
}
};
struct MinFindUnit {
int mn;
int lazy = 0;
void push(MinFindUnit& L, MinFindUnit& R) {
if(lazy == 0) return;
L.lazy += lazy;
R.lazy += lazy;
R.mn += lazy;
L.mn += lazy;
lazy = 0;
return;
}
void pull(MinFindUnit& L, MinFindUnit& R) {
mn = min(L.mn, R.mn);
return;
}
};
struct MinFind : AINT<MinFindUnit> {
int query_next(int t, int limit) {
if(aint[1].mn > limit) return -1;
for(int itt = 0; itt < 2; itt++) {
walk([&](auto& a, int cl, int cr) {
if(t < cl) return 0;
if(cr < t) return 0;
if(a.mn > limit) {
t = cr + 1;
return 0;
}
if(cl == cr) { return 0; }
return 1;
}, t, n - 1);
if(t == n) t = 0;
}
return t;
}
int query_prev(int t, int limit) {
if(aint[1].mn > limit) return -1;
for(int itt = 0; itt < 2; itt++) {
walk<1>([&](auto& a, int cl, int cr) {
if(t < cl) return 0;
if(cr < t) return 0;
if(a.mn > limit) {
t = cl - 1;
return 0;
}
if(cl == cr) { return 0; }
return 1;
}, 0, t);
if(t == -1) t = n - 1;
}
return t;
}
void add(int l, int r, int x) {
if(l > r) { add(l, N - 1, x), add(0, r, x); return; }
walk([&](auto& a, int cl, int cr) {
a.mn += x;
a.lazy += x;
return 0;
}, l, r);
}
void set(int p, int x) {
set(p, p, x);
}
void set(int l, int r, int x) {
walk([&](auto& a, int cl, int cr) {
if(cl != cr) return 1;
a.mn = x;
a.lazy = 0;
return 0;
}, l, r);
}
int query(int l, int r, int x = 1e9 + 6) {
if(l > r) return min(query(l, N - 1), query(0, r));
walk([&](auto& a, int cl, int cr) {
x = min(x, a.mn);
return 0;
}, l, r);
return x;
}
};
MinFind nextinqueue;
namespace Queue {
int next[nmax];
MinFind inside;
auto rdist = [](int x, int d) {
return d < x? N - x + d : d - x;
};
auto ldist = [](int x, int d) {
return d <= x? x - d : x + N - d;
};
set<int> heads;
void init() {
inside.init(N);
inside.set(0, N - 1, 1);
}
void insert(int node) {
nextinqueue.set(node, 1e9 + 5);
heads.emplace(node);
inside.set(node, 0);
next[node] = -1;
int nx = inside.query_next((node + 1) % N, 0);
int pr = inside.query_prev((node - 1 + N) % N, 0);
if(nx != node && rdist(node, nx) < K) {
next[node] = nx;
if(heads.count(nx)) heads.erase(nx);
}
if(pr != node && ldist(node, pr) < K) {
heads.erase(node);
next[pr] = node;
}
}
vector<int> prune() {
vector<int> rez;
for(auto x : heads)
rez.emplace_back(x), inside.set(x, 1);
heads.clear();
for(auto x : rez)
if(next[x] != -1) heads.emplace(next[x]);
return rez;
}
}
vector<int> topsort;
#define left ofia
#define right goa
int left[nmax][18], jumpl[nmax][18];
int right[nmax][18], jumpr[nmax][18];
void init(int k__, std::vector<int> r) {
auto T = r;
K = k__;
N = sz(r);
topsort.resize(N);
Queue::init();
nextinqueue.init(N);
vector<int> erased(N, 0);
nextinqueue.walk([&](auto& a, int cl, int cr) {
if(cl != cr) return 1;
a.mn = r[cl];
return 0;
});
for(int i = 0; i < sz(r); i++)
if(r[i] == 0) erased[i] = 1, Queue::insert(i);
int color = 0;
while(sz(Queue::heads)) {
auto rem = Queue::prune();
++color;
for(auto x : rem) topsort[x] = color;
for(auto x : rem)
nextinqueue.add((x - K + 1 + N) % N, x, -1);
while(1) {
int x = nextinqueue.query_next(0, 0);
if(x == -1) break;
Queue::insert(x);
}
}
vector<int> idx(N);
iota(all(idx), 0);
sort(all(idx), [&](int a, int b) { return topsort[a] > topsort[b]; });
MinFind inserted;
inserted.init(N);
inserted.set(0, N - 1, 1e9 + 5);
for(auto x : idx) {
inserted.set(x, topsort[x]);
int mn = inserted.query_prev(x, inserted.query((x - K + 1 + N) % N, x));
mn = (mn == -1? x : mn);
jumpl[x][0] = mn <= x? x - mn : x + N - mn;
if(jumpl[x][0] >= K) { mn = x; }
else if(topsort[mn] <= topsort[x]) mn = x;
left[x][0] = mn;
jumpl[x][0] = mn <= x? x - mn : x + N - mn;
mn = inserted.query_next(x, inserted.query(x, (x + K - 1) % N));
mn = (mn == -1? x : mn);
jumpr[x][0] = (mn >= x? mn - x : N - x + mn);
if(jumpr[x][0] >= K) { mn = x; }
else if(topsort[mn] <= topsort[x]) mn = x;
jumpr[x][0] = (mn >= x? mn - x : N - x + mn);
right[x][0] = mn;
}
for(int step = 1; step < 18; step++)
for(int i = 0; i < N; i++)
left[i][step] = left[left[i][step - 1]][step - 1], jumpl[i][step] = jumpl[i][step - 1] + jumpl[left[i][step - 1]][step - 1],
right[i][step] = right[right[i][step - 1]][step - 1], jumpr[i][step] = jumpr[i][step - 1] + jumpr[right[i][step - 1]][step - 1];
return;
}
bool compare_smaller(int x, int y) {
auto rdist = [&](int d) {
return d < x? N - x + d : d - x;
};
auto ldist = [&](int d) {
return d <= x? x - d : x + N - d;
};
int st = x, buffer = rdist(y);
for(int i = 17; i >= 0; i--) {
if(buffer < jumpr[st][i]) continue;
buffer -= jumpr[st][i];
st = right[st][i];
}
if(st == y) return 1;
if(rdist(y) - rdist(st) < K && topsort[y] > topsort[st]) return 1;
st = x;
buffer = ldist(y);
for(int i = 17; i >= 0; i--) {
if(buffer < jumpl[st][i]) continue;
buffer -= jumpl[st][i];
st = left[st][i];
}
if(st == y) return 1;
if(ldist(y) - ldist(st) < K && topsort[y] > topsort[st]) return 1;
return 0;
}
int compare_plants(int x, int y) {
return compare_smaller(x, y)? 1 : compare_smaller(y, x)? -1 : 0;
}
