#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi19/day2/debug.h"
#else
#define debug(...) void(37)
#endif
const int inf = int(1e9);
struct SegTree {
struct node {
array<int, 2> mn{};
int tag = 0;
node operator+(node x) {
node res;
res.mn = min(mn, x.mn);
return res;
}
void modify(int x) {
tag += x;
mn[0] += x;
}
};
vector<node> tree;
int n;
void push(int v, int rv) {
tree[v + 1].modify(tree[v].tag);
tree[rv].modify(tree[v].tag);
tree[v].tag = 0;
}
#define def int mid = (l + r) >> 1, rv = v + ((mid - l + 1) << 1)
void modify(int v, int l, int r, int ll, int rr, int x) {
debug(v, l, r, ll, rr, x);
if (l >= ll && rr >= r) {
if (l == r) {
tree[v].mn[1] = l;
}
tree[v].modify(x);
debug(v, l, r, tree[v].mn);
return;
}
def;
push(v, rv);
if (mid >= ll) {
modify(v + 1, l, mid, ll, rr, x);
}
if (mid < rr) {
modify(rv, mid + 1, r, ll, rr, x);
}
tree[v] = tree[v + 1] + tree[rv];
debug(v, l, r, tree[v].mn);
}
array<int, 2> root() {
return tree[0].mn;
}
void modify(int l, int r, int x) {
modify(0, 0, n - 1, l, r, x);
}
SegTree(int _n) : n(_n) {
tree.resize(n * 2);
}
};
int N, K, LG;
vector<int> ord;
vector<vector<int>> liftL, liftR;
vector<vector<long long>> distL, distR;
int L_dist(int from, int to) {
return (from >= to ? from - to : from + N - to);
}
int R_dist(int from, int to) {
return (from <= to ? to - from : to + N - from);
}
void init(int _K, std::vector<int> R) {
reverse(R.begin(), R.end());
N = int(R.size());
K = _K;
LG = __lg(N) + 1;
SegTree st(N);
for (int i = 0; i < N; ++i) {
st.modify(i, i, +R[i]);
}
debug(N, K, LG, R);
set<int> act;
set<pair<int, int>> dists;
vector<int> cur_len(N, -1);
vector<int> use;
auto Upd_len = [&](int x) {
debug("upd after", x);
if (act.empty()) {
return;
}
auto it = act.lower_bound(x);
if (it == act.begin()) {
it = act.end();
}
it = prev(it);
x = *it;
debug("upd", x);
//debug(dists);
if (cur_len[x] != -1) {
dists.erase(dists.find(pair{cur_len[x], x}));
}
it = next(it);
if (it == act.end()) {
int from = *act.begin();
cur_len[x] = from + N - x;
} else {
cur_len[x] = *it - x;
}
dists.emplace(cur_len[x], x);
};
auto Add_seg = [&](int x) {
debug("add", x);
act.insert(x);
Upd_len(x + 1);
Upd_len(x);
};
vector<int> next(N, -1);
auto Push_segs = [&](int last) {
debug(st.root());
while (st.root()[0] == 0) {
debug("add", st.root());
int id = st.root()[1];
st.modify(id, id, +inf);
next[id] = (last == -1 ? id : last);
Add_seg(id);
}
};
Push_segs(-1);
ord.resize(N);
for (int i = 0; i < N; ++i) {
debug(dists);
assert(!dists.empty());
auto it = prev(dists.end());
auto[len, id] = *it;
debug("########################", i, len, id);
ord[id] = i;
assert(len >= K);
dists.erase(it);
act.erase(id);
Upd_len(id);
int r = id + K - 1;
debug("upd seg tree");
if (r < N) {
debug(id, r);
st.modify(id, r, -1);
} else {
debug(id, N - 1);
debug(0, r);
r %= N;
st.modify(id, N - 1, -1);
st.modify(0, r, -1);
}
Push_segs(id);
}
liftL.resize(LG, vector<int>(N));
liftR.resize(LG, vector<int>(N));
distL.resize(LG, vector<long long>(N));
distR.resize(LG, vector<long long>(N));
set<pair<int, int>> mx;
for (int i = 1; i < K; ++i) {
mx.emplace(ord[i], i);
}
for (int i = 0; i < N; ++i) {
auto it = mx.lower_bound(pair{ord[i], -1});
liftR[0][i] = (it == mx.begin() ? i : prev(it)->second);
int add = (i + K) % N;
mx.emplace(ord[add], add);
int rem = (i + 1) % N;
mx.erase(pair{ord[rem], rem});
}
mx.clear();
for (int i = 1; i < K; ++i) {
mx.emplace(ord[N - i], N - i);
}
for (int i = 0; i < N; ++i) {
debug(i, mx);
auto it = mx.lower_bound(pair{ord[i], -1});
liftL[0][i] = (it == mx.begin() ? i : prev(it)->second);
mx.emplace(ord[i], i);
int rem = (N - K + i + 1) % N;
mx.erase(pair{ord[rem], rem});
}
for (int i = 0; i < N; ++i) {
distL[0][i] = L_dist(i, liftL[0][i]);
distR[0][i] = R_dist(i, liftR[0][i]);
}
for (int l = 1; l < LG; ++l) {
for (int i = 0; i < N; ++i) {
{
int to = liftL[l - 1][i];
liftL[l][i] = liftL[l - 1][to];
distL[l][i] = distL[l - 1][i] + distL[l - 1][to];
}
{
int to = liftR[l - 1][i];
liftR[l][i] = liftR[l - 1][to];
distR[l][i] = distR[l - 1][i] + distR[l - 1][to];
}
}
}
debug(R, ord, liftL[0], liftR[0]);
}
//#define SUBTASK3 false
int elevate(int v, int to, vector<vector<int>>& lift, vector<vector<long long>>& dist) {
for (int l = LG - 1; l >= 0; --l) {
if (dist[l][v] <= to) {
to -= dist[l][v];
v = lift[l][v];
}
}
return v;
}
bool depends(int x, int y) {
if (ord[x] > ord[y]) {
swap(x, y);
}
{
int dist = L_dist(y, x);
int go = elevate(y, dist, liftL, distL);
if (L_dist(go, x) < K && ord[x] <= ord[go]) {
return true;
}
}
{
int dist = R_dist(y, x);
int go = elevate(y, dist, liftR, distR);
if (R_dist(go, x) < K && ord[x] <= ord[go]) {
return true;
}
}
return false;
}
int compare_plants(int x, int y) {
x = N - 1 - x;
y = N - 1 - y;
debug("compare", x, y);
if (depends(x, y)) {
return (ord[x] < ord[y] ? 1 : -1);
}
return 0;
}
