#include "walk.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
const int N = 1e5 + 10;
const ll Inf = 1e18;
vector< pair<int, int> > G[N];
vector<int> x, h, l, r, y;
int n, m;
void AddEdge(int u, int v){
//cerr << "# " << u << ' ' << v << '\n';
int w = abs(y[u] - y[v]);
G[u].pb({v, w});
G[v].pb({u, w});
}
set<pii> st;
void Add(int id){
st.insert({y[id], id});
auto it = st.find({y[id], id});
if(it != st.begin())
AddEdge(id, prev(it) -> S);
if(next(it) != st.end())
AddEdge(id, next(it) -> S);
}
void Rem(int id){
st.erase({y[id], id});
}
vector<int> evA[N], evR[N];
ll dis[N];
set< pli > pq;
ll Djik(){
memset(dis, 31, sizeof dis);
for(int i = 0; i < m; i++){
if(l[i] == 0){
dis[i] = y[i];
pq.insert({dis[i], i});
}
}
int fr;
while(!pq.empty()){
fr = pq.begin() -> S;
//cerr << fr << ' ' << dis[fr] << '\n';
pq.erase(pq.begin());
for(auto [adj, w] : G[fr]){
if(dis[adj] > dis[fr] + w){
pq.erase({dis[adj], adj});
dis[adj] = dis[fr] + w;
pq.insert({dis[adj], adj});
}
}
}
ll res = Inf;
for(int i = 0; i < m; i++){
if(r[i] == n - 1)
res = min(res, dis[i] + y[i]);
}
return res == Inf ? -1 : res;
}
ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int s, int g) {
x = _x; h = _h; l = _l; r = _r; y = _y;
n = x.size(); m = y.size();
assert(s == 0 && g == n - 1);
ll ans = x[g] - x[s];
for(int i = 0; i < m; i++){
evA[l[i]].pb(i);
evR[r[i] + 1].pb(i);
}
for(int i = 0; i < n; i++){
for(auto x : evR[i]) Rem(x);
for(auto x : evA[i]) Add(x);
}
ll dij = Djik();
return dij == -1 ? -1 : dij + ans;
}
