#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define eb emplace_back
#define MP make_pair
const ll INF = 1ll << 55;
ll dijkstra(auto adj, int s, int f) {
int n = adj.size();
vector<bool> vis(n);
vector<ll> d(n, INF);
d[s] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push(MP(0, s));
while (!pq.empty()) {
auto [_, v] = pq.top();
pq.pop();
if (vis[v]) continue;
vis[v] = true;
for (auto [u, w] : adj[v]) if (d[v]+w < d[u]) {
d[u] = d[v]+w;
pq.push(MP(d[u], u));
}
}
return d[f];
}
ll 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();
int m = l.size();
vector<vector<int>> add(n), del(n);
for (int i=0; i<m; i++) {
add[l[i]].pb(i);
del[r[i]].pb(i);
}
vector<ll> cost(m, INF);
set<pair<ll, int>> S;
for (int j : add[0]) if (y[j] <= h[0]) {
S.insert(MP(y[j], j));
cost[j] = y[j];
}
auto ins = [&](int i) {
auto it = S.upper_bound(MP(y[i], m));
if (it != S.end()) {
auto [_, j] = *it;
cost[i] = min(cost[i], cost[j] + y[j]-y[i]);
}
if (it != S.begin()) {
it--;
auto [_, j] = *it;
cost[i] = min(cost[i], cost[j] + y[i]-y[j]);
}
if (cost[i] != INF) S.insert(MP(y[i], i));
};
auto rem = [&](int i) {
if (cost[i] == INF) return;
S.erase(MP(cost[i], i));
auto it = S.upper_bound(MP(y[i], m));
if (it != S.end()) {
auto [_, j] = *it;
cost[j] = min(cost[j], cost[i] + y[j]-y[i]);
}
if (it != S.begin()) {
it--;
auto [_, j] = *it;
cost[j] = min(cost[j], cost[i] + y[i]-y[j]);
}
};
for (int i=1; i<n; i++) {
for (auto j : add[i]) if (y[j] <= h[i]) ins(j);
if (i+1 != n) for (auto j : del[i]) rem(j);
}
ll ans = INF;
for (auto [_, i] : S) ans = min(ans, cost[i]+y[i] + x[n-1]-x[0]);
if (ans==INF) return -1;
return ans;
}
