#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int N = 1<<17;
int Nxt[N][20], cur;
long long Mn[9<<17];
set<pair<int, int>> st[N];
vector<pair<int, int>> nei[N];
vector<int> v;
int Find(int i, int j){
// cout<<"here "<<endl;
auto u = st[i].upper_bound({j, -1});
int vl;
if (u == st[i].end() or (*u).first > j){
vl = ++cur;
st[i].insert({j, vl});
}
// cout<<"done"<<endl;
return vl;
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int t){
int n = x.size(), m = l.size();
h.push_back(1000000005);
for (int i=0;i<=n;i++){
while (v.size() > 0 and h[v.back()] < h[i])
Nxt[v.back()][0] = i, v.pop_back();
v.push_back(i), Nxt[i][0] = n;
}
Nxt[n][0] = cur = n;
for (int i=0;i<n;i++)
// cout<<Nxt[i][0]<<' ';
// cout<<endl;
for (int j=0;j<18;j++){
for (int i=0;i<=n;i++)
Nxt[i][j+1] = Nxt[Nxt[i][j]][j];
}
for (int i=0;i<m;i++){
int f = Find(l[i], y[i]);
// cout<<i<<endl;
// cout<<" :: ";
while (l[i] != r[i]){
int nx = l[i] + 1;
for (int j=18;j+1;j--){
if (h[Nxt[nx][j]] < y[i])
nx = Nxt[nx][j];
}
if (h[nx] < y[i])
nx = Nxt[nx][0];
// cout<<nx<<' ';
int F = Find(nx, y[i]);
nei[f].push_back({F, x[nx] - x[l[i]]});
nei[F].push_back({f, x[nx] - x[l[i]]});
l[i] = nx, f = F;
}
// cout<<endl;
}
// return 0;
for (int i=0;i<n;i++){
int lst = i + 1, Hei = 0;
for (auto [hei, j] : st[i]){
nei[lst].push_back({j, hei - Hei});
nei[j].push_back({lst, hei - Hei});
Hei = hei;
lst = j;
}
}
// return 0;
for (int i=1;i<=cur;i++)
Mn[i] = 1e15 * (i != s + 1);
priority_queue<pair<long long, int>> pq;
pq.push({0, s + 1});
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});
}
}
}
if (Mn[t + 1] == 1e15)
return -1;
return Mn[t + 1];
}
