#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
const int N = 1<<17;
vector<pair<int, int>> nei[N * 18], vs[2], vg[2];
vector<int> ins[N], ers[N], L, R;
map<int, int> hor[N], ver[N];
long long Mn[N * 18];
int cur;
int FindVer(int i, int j){
int &vl = ver[i][j];
if (vl == 0)
vl = cur++;
return vl;
}
void FindHor(int i, int j, int y){
if (L[i] > j or j > R[i])
return;
int &vl = hor[i][j];
if (vl == 0)
vl = FindVer(j, y);
}
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();
L = l, R = r;
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);
FindHor(i, l[i], y[i]);
FindHor(i, r[i], y[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])
FindHor(i, (*u).second, y[i]);
};
add(vs[0]);
add(vs[1]);
add(vg[0]);
add(vg[1]);
}
set<pair<int, int>> ms;
for (int i=0;i<n;i++){
for (int j : ins[i])
ms.insert({y[j], j});
set<int> cnd;
for (auto pr : ver[i]){
auto u = ms.upper_bound({pr.first+1, -1});
if (u != ms.end() and (*u).first <= h[i])
cnd.insert((*u).second);
if (u == begin(ms))
continue;
if ((*u).first == pr.first){
if (u == begin(ms))
continue;
u = prev(u);
}
cnd.insert((*u).second);
}
for (int j : ers[i])
ms.erase({y[j], j});
for (int j : cnd)
FindHor(j, i, y[j]);
}
for (int i=0;i<n;i++){
if (i == s or i == g)
FindVer(i, 0);
pair<int, int> lst = {-1, -1};
// cout<<i<<" :: ";
for (auto Now : ver[i]){
if (Now.first > h[i])
break;
if (lst.first != -1){
int D = Now.first - lst.first;
// cout<<i<<','<<lst.first<<" --> "<<i<<','<<Now.first<<" | ";
nei[lst.second].push_back({Now.second, D});
nei[Now.second].push_back({lst.second, D});
}
lst = Now;
}
// cout<<endl;
}
for (int i=0;i<n;i++){
pair<int, int> lst = {-1, -1};
// cout<<i<<" ::: ";
for (auto Now : hor[i]){
if (lst.first != -1){
int D = x[Now.first] - x[lst.first];
// cout<<lst.first<<','<<y[lst.first]<<" --> "<<Now.first<<','<<y[Now.first]<<" | ";
nei[lst.second].push_back({Now.second, D});
nei[Now.second].push_back({lst.second, D});
}
lst = Now;
}
// cout<<endl;
}
for (int i=0;i<=cur;i++)
Mn[i] = 1e15;
Mn[ver[s][0]] = 0;
priority_queue<pair<long long, int>> pq;
pq.push({0, ver[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[ver[g][0]] == 1e15 ? -1 : Mn[ver[g][0]]);
}
