#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
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[9<<17];
vector<int> v;
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;
}
long long solve1(vector<int> x, vector<int> l, vector<int> r, vector<int> y, int s, int t){
if (s > t)
swap(s, t);
long long L = 0, R = 1e9 + 7, n = x.size(), m = l.size();
vector<pair<int, pair<int, int>>> vec;
for (int i=0;i<m;i++)
vec.push_back({l[i], {r[i], y[i]}});
sort(begin(vec), end(vec));
while (L + 1 < R){
int mid = (L + R) / 2, mx = s;
for (int i=0;i<m;i++){
if (vec[i].second.second <= mid and vec[i].first <= mx)
mx = max(mx, vec[i].second.first);
}
if (mx >= t)
R = mid;
else
L = mid;
}
return 1LL * R * 2 + x[t] - x[s];
}
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(), tt = 1;
for (int i=0;i<n;i++)
tt &= (h[i] == h[0]);
if (tt){
return solve1(x, l, r, y, s, t);
}
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;
}
cur = n;
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]);
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];
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;
}
}
for (int i=0;i<n;i++){
int lst = i, 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;
}
}
for (int i=0;i<=cur;i++)
Mn[i] = 1e15 * (i != s);
priority_queue<pair<long long, int>> pq;
pq.push({0, s});
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] == 1e15)
return -1;
return Mn[t];
}
