#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e17;
vector<vector<pair<int, int>>> graph;
int n, m;
int get_idx(int build, vector<pair<int, int>> &foundIn) {
for (auto [b, i]: foundIn) {
if (b == build) return i;
}
return -1;
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
n = x.size();
m = l.size();
vector<vector<tuple<int, int, ll>>> inter(n);
for (int i = 0; i < m; i++) {
for (int j = l[i]; j <= r[i]; j++) {
if (h[j] < y[i]) continue;
inter[j].push_back({y[i], i, INF});
}
}
for (int i = 0; i < n; i++) sort(inter[i].begin(), inter[i].end());
// {min distance, building, skyline index}
priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
for (int i = 0; i < (int)inter[s].size(); i++) {
int skyline = get<1>(inter[s][i]);
pq.push({y[skyline], s, skyline});
inter[s][i] = {y[skyline], skyline, y[skyline]};
}
vector<vector<pair<int, int>>> foundIn(m);
for (int i = 0; i < n; i++) {
int sz = inter[i].size();
for (int j = 0; j < sz; j++) {
foundIn[get<1>(inter[i][j])].push_back({i, j});
}
}
while (!pq.empty()) {
ll dis = get<0>(pq.top());
int build = get<1>(pq.top());
int skyline = get<2>(pq.top());
pq.pop();
int idx = get_idx(build, foundIn[skyline]);
if (get<2>(inter[build][idx]) != dis) continue;
int sz = inter[build].size();
for (auto [nxtBuild, idx2]: foundIn[skyline]) {
if (nxtBuild == build || h[nxtBuild] < y[skyline]) continue;
//int idx2 = get_idx(skyline, inter[nxtBuild], y[skyline]);
ll dis2 = abs(x[build] - x[nxtBuild]);
if (dis2 + dis < get<2>(inter[nxtBuild][idx2])) {
pq.push({dis2 + dis, nxtBuild, skyline});
inter[nxtBuild][idx2] = {y[skyline], skyline, dis + dis2};
}
}
if (idx + 1 < sz) {
int skyline2 = get<1>(inter[build][idx+1]);
ll dis2 = y[skyline2] - y[skyline];
int idx2 = idx+1;
if (dis2 + dis < get<2>(inter[build][idx2])) {
pq.push({dis2 + dis, build, skyline2});
inter[build][idx2] = {y[skyline2], skyline2, dis + dis2};
}
}
if (idx > 0) {
int skyline2 = get<1>(inter[build][idx-1]);
ll dis2 = y[skyline] - y[skyline2];
int idx2 = idx-1;
if (dis2 + dis < get<2>(inter[build][idx2])) {
pq.push({dis2 + dis, build, skyline2});
inter[build][idx2] = {y[skyline2], skyline2, dis + dis2};
}
}
}
ll ans = INF;
for (int i = 0; i < (int)inter[g].size(); i++) {
ans = min(ans, get<2>(inter[g][i]) + y[get<1>(inter[g][i])]);
}
if (ans == INF) return -1;
else return ans;
}
