#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
const int N = 1<<17;
vector<pair<int, int>> nei[N * 32], vs[2], vg[2];
vector<int> hei[N], ins[N], ers[N], vec[N];
set<pair<int, int>> st[N];
long long Mn[N * 32];
int cur;
int Find(int i, int j, int vl = 0){
auto u = st[i].upper_bound({j, -1});
if (u == st[i].end() or (*u).first > j){
vl = cur++;
st[i].insert({j, vl});
}
else
vl = (*u).second;
return vl;
}
void uniquify(vector<int> &v){
sort(begin(v), end(v));
v.resize(unique(begin(v), end(v)) - begin(v));
}
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(), m = l.size();
if (s > g)
swap(s, g);
auto make = [=](vector<pair<int, int>> &v, int st, int en, int stp){
for (int i=st, mx = 0; i != en; i += stp)
if (h[i] > mx)
mx = h[i], v.push_back({mx, i});
};
make(vs[0], s, -1, -1);
make(vs[1], s, n, 1);
make(vg[0], g, -1, -1);
make(vg[1], g, n, 1);
////////////////////////////////////////////////////////////
for (int i=0;i<m;i++){
ins[l[i]].push_back(i);
ers[r[i]].push_back(i);
vec[i] = {l[i], r[i]};
auto add = [=](vector<pair<int, int>> &v){
auto u = upper_bound(begin(v), end(v), make_pair(y[i], -1));
if (u != end(v) and l[i] <= (*u).second and (*u).second <= r[i])
vec[i].push_back((*u).second);
};
// add(vs[0]);
// add(vs[1]);
// add(vg[0]);
// add(vg[1]);
uniquify(vec[i]);
for (int j : vec[i])
hei[j].push_back(y[i]);
}
set<pair<int, int>> ms;
for (int i=0;i<n;i++){
for (int j : ins[i])
ms.insert({y[j], j});
for (int j=hei[i].size()-1;j>=0;j--){
auto u = ms.upper_bound({hei[i][j], -1});
if (u != ms.end() and (*u).first <= h[i])
hei[i].push_back((*u).first), vec[(*u).second].push_back(i);
if (u != begin(ms))
u = prev(u), hei[i].push_back((*u).first), vec[(*u).second].push_back(i);
}
for (int j : ers[i])
ms.erase({y[j], j});
if (i == s or i == g)
hei[i].push_back(0);
uniquify(hei[i]);
for (int j=0, f, F;j<hei[i].size();j++){
f = F, F = Find(i, hei[i][j]);
if (j){
nei[f].push_back({F, hei[i][j] - hei[i][j-1]});
nei[F].push_back({f, hei[i][j] - hei[i][j-1]});
}
}
}
for (int i=0;i<m;i++){
uniquify(vec[i]);
int L, f, F;
for (int j=0;j<vec[i].size();j++){
f = F, F = Find(vec[i][j], y[i]);
if (j){
nei[f].push_back({F, x[vec[i][j]] - x[L]});
nei[F].push_back({f, x[vec[i][j]] - x[L]});
}
L = vec[i][j];
}
}
for (int i=0;i<=cur;i++)
Mn[i] = 1e15;
Mn[Find(s, 0)] = 0;
priority_queue<pair<long long, int>> pq;
pq.push({0, Find(s, 0)});
while (pq.size() > 0){
auto [mn, u] = pq.top();
pq.pop();
mn = -mn;
if (mn != Mn[u])
continue;
for (auto [i, w] : nei[u]){
if (Mn[i] > Mn[u] + w)
Mn[i] = Mn[u] + w, pq.push({-Mn[i], i});
}
}
return (Mn[Find(g, 0)] == 1e15 ? -1 : Mn[Find(g, 0)]);
}
