#include "walk.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector <int> arr;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int MAXN = 1e5+5, MAXT = 6e5+5;
const ll INF = 1e18;
int N, M, S[2], T;
ll dist[MAXT];
map <int,int> ver[MAXN];
vector <pii> adj[MAXT];
priority_queue <pli,vector<pli>,greater<pli> > PQ;
int get(int x,int y) {
int &p = ver[x][y];
if (!p) {
T++;
p = T;
}
return p;
}
ll min_distance(arr X,arr H,arr L,arr R,arr Y,int st,int fn) {
N = X.size();
M = Y.size();
S[0] = st;
S[1] = fn;
get(st,0);
get(fn,0);
for (int i=0;i<M;i++) {
set <int> hor;
hor.insert(L[i]);
hor.insert(R[i]);
for (int j=L[i];j<=R[i];j++) {
if (H[j] >= Y[i]) {
hor.insert(j);
}
}
for (int t=0;t<2;t++) {
if (S[t] <= L[i] || S[t] >= R[i]) continue;
for (int j=S[t];1;j--) {
if (H[j] >= Y[i]) {
hor.insert(j);
break;
}
}
for (int j=S[t];1;j++) {
if (H[j] >= Y[i]) {
hor.insert(j);
break;
}
}
}
vector <pii> pt;
for (auto x : hor) {
pt.push_back({x,get(x,Y[i])});
}
for (int i=1;i<pt.size();i++) {
int d = X[pt[i].fi]-X[pt[i-1].fi];
adj[pt[i].se].push_back({pt[i-1].se,d});
adj[pt[i-1].se].push_back({pt[i].se,d});
}
}
for (int i=0;i<N;i++) {
pii last = {-1,-1};
for (auto x : ver[i]) {
if (last.fi != -1) {
adj[x.se].push_back({last.se,x.fi-last.fi});
adj[last.se].push_back({x.se,x.fi-last.fi});
}
last = x;
}
}
PQ.push({0,1});
for (int i=2;i<=T;i++) {
dist[i] = INF;
}
while (!PQ.empty()) {
pli x = PQ.top();
PQ.pop();
if (dist[x.se] != x.fi) continue;
for (pii y : adj[x.se]) {
if (dist[y.fi] <= x.fi + y.se) continue;
dist[y.fi] = x.fi + y.se;
PQ.push({dist[y.fi],y.fi});
}
}
if (dist[2] == INF) {
return -1;
}
return dist[2];
}
