#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
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<pair<int,int>>> g(m+2);
vector<vector<int>> ev;
for (int i=0; i<m; i++){
ev.push_back({l[i], 1, i});
ev.push_back({r[i], -1, i});
}
set<int> hs;
map<int,int> htw;
sort(ev.begin(), ev.end());
int i = 0;
//cout << "a" << endl;
while (i < ev.size()){
//cout << i << endl;
int ct = ev[i][0];
set<int> rm;
while (i < ev.size() && ev[i][0] == ct && ev[i][1] == -1){
hs.erase(y[ev[i][2]]);
rm.insert(ev[i][2]);
i++;
}
while (i < ev.size() && ev[i][0] == ct && ev[i][1] == 1){
hs.insert(y[ev[i][2]]);
htw[y[ev[i][2]]] = ev[i][2];
i++;
}
//cout << "b" << endl;
for (int w : rm){
auto it = hs.upper_bound(y[w]);
if (it != hs.end()) g[w].push_back({htw[*it], *it-y[w]});
if (it != hs.begin()) it--;
if (1){
g[w].push_back({htw[*it], y[w]-*it});
if (*it == y[w]){
it--;
if (it != hs.begin()) g[w].push_back({htw[*it], y[w]-*it});
}
}
}
if (ct == 0 && !hs.empty()) g[m].push_back({htw[*hs.begin()], *hs.begin()});
if (ct == n-1){
for (int w : rm) g[w].push_back({m+1, y[w]});
}
}
/*for (int i=0; i<=m+1; i++){
cout << i << endl;
for (pair<int,int> next : g[i]) cout << next.first << " " << next.second << endl;
}*/
priority_queue<pair<ll,int>> pq;
vector<bool> seen(m+2, false);
pq.push({0, m});
//cout << "c" << endl;
while (!pq.empty()){
ll d = -pq.top().first;
int cur = pq.top().second;
pq.pop();
if (seen[cur]) continue;
seen[cur] = true;
if (cur == m+1) return d+(ll)(x[n-1]-x[0]);
for (pair<int,int> next : g[cur]) pq.push({-(d+next.second), next.first});
}
return -1;
}
