#include <bits/stdc++.h>
#include "walk.h"
using ll = long long;
template <class T> using Vec = std::vector<T>;
constexpr ll INF = std::numeric_limits<ll>::max() / 2;
struct RMQ {
int size;
Vec<ll> min;
RMQ(const int n): size(n), min(2 * n, INF) {}
void assign(int i, const ll x) {
i += size;
min[i] = x;
while (i > 1) {
i >>= 1;
min[i] = std::min(min[2 * i], min[2 * i + 1]);
}
}
ll fold(int l, int r) const {
l += size;
r += size;
ll x = INF;
while (l < r) {
if (l & 1) x = std::min(x, min[l++]);
if (r & 1) x = std::min(x, min[--r]);
l >>= 1;
r >>= 1;
}
return x;
}
};
ll min_distance(Vec<int> x, Vec<int> h, Vec<int> l, Vec<int> r, Vec<int> y, int s, int g) {
const int n = (int) x.size();
const int m = (int) y.size();
if (s == 0 and g == n - 1) {
Vec<Vec<int>> start(n), end(n);
for (int i = 0; i < m; ++i) {
start[l[i]].push_back(i);
end[r[i]].push_back(i);
}
Vec<int> cmp = y;
std::sort(cmp.begin(), cmp.end());
cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
Vec<int> idx(m);
for (int i = 0; i < m; ++i) {
idx[i] = std::lower_bound(cmp.begin(), cmp.end(), y[i]) - cmp.begin();
}
const int sz = (int) cmp.size();
RMQ down(sz), up(sz);
Vec<int> alive(sz);
for (const int j: start[0]) {
down.assign(idx[j], y[j] - y[j]);
up.assign(idx[j], y[j] + y[j]);
alive[idx[j]] += 1;
}
for (int i = 1; i < n; ++i) {
const int height = std::upper_bound(cmp.begin(), cmp.end(), h[i]) - cmp.begin();
for (const auto j: start[i]) {
const ll a = down.fold(0, idx[j] + 1);
const ll b = up.fold(idx[j], height);
ll d = INF;
if (a != INF) {
d = std::min(d, a + y[j]);
}
if (b != INF) {
d = std::min(d, b - y[j]);
}
if (d != INF) {
down.assign(idx[j], d - y[j]);
up.assign(idx[j], d + y[j]);
} else {
down.assign(idx[j], INF);
down.assign(idx[j], INF);
}
alive[idx[j]] += 1;
}
if (i != n - 1) {
for (const auto j: end[i]) {
alive[idx[j]] -= 1;
if (alive[idx[j]] == 0) {
down.assign(idx[j], INF);
up.assign(idx[j], INF);
}
}
}
}
ll ret = up.fold(0, sz);
return ret == INF ? -1 : (ret + x[n - 1] - x[0]);
}
return -1;
}
