//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
const ll LLINF = (ll)1e18 + 10;
ll min_distance(ve<int> X, ve<int> H, ve<int> L, ve<int> R, ve<int> Y, int s, int g) {
int n = (int)X.size();
int m = (int)L.size();
ve<tuple<int, int, int>> E;
ve<ve<pii>> S(n);
ve<pii> P(m, {-1, -1});
ve<ll> D;
ve<ve<pair<int, ll>>> G(n);
priority_queue<pair<ll, int>, ve<pair<ll, int>>, greater<pair<ll, int>>> pq;
for (int i = 0; i < n; i++) {
S[i].push_back({i, 0});
E.push_back({i, 1, -1});
}
for (int i = 0; i < m; i++) {
E.push_back({L[i], 0, i});
E.push_back({R[i], 2, i});
}
sort(E.begin(), E.end());
set<pii> A;
for (tuple<int, int, int> e : E) {
if (get<1>(e) == 0) {
int j = get<2>(e);
A.insert({Y[j], j});
}
else if (get<1>(e) == 1) {
int i = get<0>(e);
for (pii a : A) {
int j, y;
tie(y, j) = a;
if (y > H[i]) break;
int u = (int)G.size();
G.push_back({});
if (P[j].first != -1) {
ll w = X[i] - P[j].second;
int v = P[j].first;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
P[j] = {u, X[i]};
S[i].push_back({u, y});
}
}
else {
int j = get<2>(e);
A.erase({Y[j], j});
}
}
for (int i = 0; i < n; i++) {
for (int j = 1; j < (int)S[i].size(); j++) {
ll w = S[i][j].second - S[i][j - 1].second;
int u = S[i][j].first;
int v = S[i][j - 1].first;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
}
D = ve<ll>(G.size(), LLINF);
pq.push({0, s});
while (!pq.empty()) {
int u;
ll d;
tie(d, u) = pq.top();
pq.pop();
if (D[u] != LLINF) continue;
D[u] = d;
for (pair<int, ll> e : G[u]) {
pq.push({d + e.second, e.first});
}
}
if (D[g] == LLINF) return -1;
else return D[g];
}
