#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
int curVal, n;
vector<int> p, Left[18], Right[18];
struct SegmentTree{
int n;
vector<int> d, lazy;
void build(int id, int l, int r, const vector<int> &a){
if (l == r){
d[id] = a[l];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid, a);
build(id << 1 | 1, mid + 1, r, a);
d[id] = min(d[id << 1], d[id << 1 | 1]);
}
void init(const vector<int> &a){
n = a.size();
d.assign(n * 4 + 1, 0);
lazy.assign(n * 4 + 1, 0);
build(1, 0, n - 1, a);
}
void doLazy(int id, int l, int r){
d[id] += lazy[id];
if (l < r){
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
}
lazy[id] = 0;
return;
}
void update(int id, int l, int r, int u, int v, int val){
doLazy(id, l, r);
if (v < l || r < u)
return;
if (u <= l && r <= v){
lazy[id] += val;
doLazy(id, l, r);
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
d[id] = min(d[id << 1], d[id << 1 | 1]);
}
int getMin(int id, int l, int r, int u, int v){
doLazy(id, l, r);
if (v < l || r < u)
return 1e9;
if (u <= l && r <= v)
return d[id];
int mid = (l + r) >> 1;
return min(getMin(id << 1, l, mid, u, v), getMin(id << 1 | 1, mid + 1, r, u, v));
}
int getMin(int l, int r){
if (l <= r)
return getMin(1, 0, n - 1, l, r);
else
return min(getMin(1, 0, n - 1, l, n - 1), getMin(1, 0, n - 1, 0, r));
}
void update(int l, int r, int val){
if (l <= r){
update(1, 0, n - 1, l, r, val);
} else {
update(1, 0, n - 1, l, n - 1, val);
update(1, 0, n - 1, 0, r, val);
}
}
int findPos0(int id, int l, int r, int u, int v){
doLazy(id, l, r);
if (v < l || r < u || d[id] > 0)
return -1;
if (l == r)
return l;
int mid = (l + r) >> 1;
int res = findPos0(id << 1, l, mid, u, v);
if (res == -1)
res = findPos0(id << 1 | 1, mid + 1, r, u, v);
return res;
}
int findPos0(int l, int r){
if (l <= r)
return findPos0(1, 0, n - 1, l, r);
int res = findPos0(1, 0, n - 1, l, n - 1);
if (res == -1)
res = findPos0(1, 0, n - 1, 0, r);
return res;
}
} st;
void process(int pos, int n, int k){
while (true){
int nxt = st.findPos0((pos - k + 1 + n) % n, (pos - 1 + n) % n);
if (nxt == -1)
break;
else
process(nxt, n, k);
}
p[pos] = curVal--;
st.update(pos, pos, 1e9);
st.update((pos - k + 1 + n) % n, (pos - 1 + n) % n, -1);
}
int dist(int x, int y, int n){
if (x <= y)
return y - x;
return n - x + y;
}
void init(int k, vector<int> r) {
n = r.size();
p.assign(n, -1);
st.init(r);
curVal = n - 1;
while (curVal >= 0){
int pos = st.findPos0(0, n - 1);
assert(pos != -1);
process(pos, n, k);
}
for(int i = 0; i < 18; i++){
Left[i].assign(n, -1);
Right[i].assign(n, -1);
}
vector<int> ord(n);
for(int i = 0; i < n; i++)
ord[p[i]] = i;
st.init(vector<int>(n, 1e9));
for(int i = 0; i < n; i++){
int p = ord[i];
int x = -st.getMin((p - k + 1 + n) % n, (p - 1 + n) % n);
Left[0][p] = (x >= 0? ord[x] : p);
Left[0][p] = dist(Left[0][p], p, n);
x = -st.getMin((p + 1) % n, (p + k - 1) % n);
Right[0][p] = (x >= 0? ord[x] : p);
Right[0][p] = dist(p, Right[0][p], n);
st.update(p, p, -1e9 - i);
}
for(int i = 1; i <= 17; i++)
for(int u = 0; u < n; u++){
Left[i][u] = Left[i - 1][u] + Left[i - 1][(u - Left[i - 1][u] % n + n) % n];
Right[i][u] = Right[i - 1][u] + Right[i - 1][(u + Right[i - 1][u]) % n];
}
return;
}
int compare_plants(int x, int y) {
int u;
u = x;
for(int i = 17; i >= 0; i--)
if (dist(u, x, n) + Left[i][u] < dist(y, x, n))
u = (u - Left[i][u] + n) % n;
if (Left[0][u] > 0 && p[u] > p[y])
return 1;
u = x;
for(int i = 17; i >= 0; i--)
if (dist(x, u, n) + Right[i][u] < dist(x, y, n))
u = (u + Right[i][u] + n) % n;
if (Right[0][u] > 0 && p[u] > p[y])
return 1;
u = y;
for(int i = 17; i >= 0; i--)
if (dist(u, y, n) + Left[i][u] < dist(x, y, n))
u = (u - Left[i][u] + n) % n;
if (Left[0][u] > 0 && p[u] > p[x])
return -1;
u = y;
for(int i = 17; i >= 0; i--)
if (dist(y, u, n) + Right[i][u] < dist(y, x, n))
u = (u + Right[i][u]) % n;
if (Right[0][u] > 0 && p[u] > p[x])
return -1;
return 0;
}
