#include "walk.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
template<typename T, class F = function<T(const T&, const T&)>>
struct SparseTable {
vector<vector<T>> v;
F f;
SparseTable() { };
SparseTable(vector<T> a, F _f) : f(_f) {
int n = (int) a.size();
a.resize(n);
int lg = 32 - __builtin_clz(n);
v.resize(lg);
v[0] = a;
for (int j = 1; j < lg; j++) {
v[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++) {
v[j][i] = f(v[j - 1][i], v[j - 1][i + (1 << (j - 1))]);
}
}
}
T query(int l, int r) {
int lg = 31 - __builtin_clz(r - l + 1);
return f(v[lg][l], v[lg][r - (1 << lg) + 1]);
}
};
const int mxN = 5e6 + 5;
vector<pair<int, int>> ad[mxN];
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
int n = x.size();
int m = y.size();
vector<int> ys[n];
vector<int> up[n];;
SparseTable st(h, [&](auto i, auto j) { return max(i, j); });
for (int i = 0; i < m; i++) {
up[l[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
ys[i].push_back(0);
ys[i].push_back(h[i]);
}
vector<tuple<int, int, int>> edges;
for (int i = 0; i < n; i++) {
for (int j : up[i]) {
ys[i].push_back(y[j]);
if (r[j] == i) continue;
int hi = r[j], lo = i + 1;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (st.query(i + 1, mid) >= y[j]) hi = mid;
else lo = mid + 1;
}
edges.push_back({i, lo, y[j]});
up[lo].push_back(j);
}
up[i].clear();
}
for (int i = 0; i < n; i++) {
sort(ys[i].begin(), ys[i].end());
ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
}
map<pair<int, int>, int> id;
int cur = 0;
map<int, pair<int, int>> who;
for (int i = 0; i < n; i++) {
int last = 0;
for (int yy : ys[i]) {
who[cur] = {i, yy};
id[{i, yy}] = cur++;
ad[id[{i, yy}]].push_back({id[{i, last}], yy - last});
ad[id[{i, last}]].push_back({id[{i, yy}], yy - last});
last = yy;
}
}
for (auto [a, b, c] : edges) {
ad[id[{a, c}]].push_back({id[{b, c}], x[b] - x[a]});
ad[id[{b, c}]].push_back({id[{a, c}], x[b] - x[a]});
}
priority_queue<pair<long long, int>> pq;
vector<long long> dist(cur, 1e18);
dist[id[{s, 0}]] = 0;
pq.push({0, id[{s, 0}]});
while (!pq.empty()) {
auto [_, u] = pq.top();
pq.pop();
if (dist[u] != -_) continue;
for (auto [v, w] : ad[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
if (dist[id[{g, 0}]] != 1e18) return dist[id[{g, 0}]];
return -1;
}
