#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#include "walk.h"
using namespace std;
const int maxn = 1e5 + 10;
const ll inf = (1LL << 60);
vector<int> poc[maxn];
vector <int> kraj[maxn];
set <pair<int, ll> > s;
map<int, int> mp;
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int st, int g) {
int n = x.size();
int m = l.size();
ll ans = x[n - 1] - x[0];
for(int i = 0; i < m; i++){
poc[l[i]].push_back(y[i]);
kraj[r[i]].push_back(y[i]);
}
s.insert({0, 0});
kraj[0].push_back(0);
// for(int i = 0; i < poc[0].size(); i++){
// int vis = poc[0][i];
// s.insert({vis, vis});
// }
for(int i = 0; i < n - 1; i++){
// cout << "tui " << i << ' ' << s.size() << endl;
if(s.empty()) return -1;
mp.clear();
for(int j = 0; j < poc[i].size(); j++){
int vis = poc[i][j];
// if(mp.find(vis) != mp.end()){
// s.insert({vis, mp[vis]});
// continue;
// }
ll cost = inf;
auto it = s.lower_bound({vis, 0});
if(it != s.end() && (*it).fi == vis){
mp[vis] = 1;
continue;
}
if(it != s.end() && (*it).fi <= h[i]) cost = (*it).se + (*it).fi - vis;
if(it != s.begin()){
it--;
cost = min(cost, (*it).se + vis - (*it).fi);
}
s.insert({vis, cost});
//cout << "insert: " << vis << ' ' << cost << endl;
}
for(int j = 0; j < kraj[i].size(); j++){
int vis = kraj[i][j];
auto it = s.lower_bound({vis, 0});
ll cost = (*it).se;
// mp[vis] = cost;
it++;
if(it != s.end() && (*it).fi <= h[i]){
ll c = cost + (*it).fi - vis;
if(c < (*it).se){
int vis2 = (*it).fi;
s.erase(it);
s.insert({vis2, c});
}
// (*it).se = min((*it).se, cost + (*it).fi - vis);
}
it = s.lower_bound({vis, 0});
if(it != s.begin()){
it--;
ll c = cost + vis - (*it).fi;
//(*it).se = min((*it).se, cost + vis - (*it).fi);
if(c < (*it).se){
int vis2 = (*it).fi;
s.erase(it);
s.insert({vis2, c});
}
it++;
}
if(mp[vis] == 0){
//cout << "erase: " << vis << ' ' << cost << endl;
s.erase({vis, cost});
}
}
}
if(s.empty()) return -1;
ll naj = inf;
auto it = s.begin();
while(it != s.end()){
naj = min(naj, (*it).fi + (*it).se);
it++;
}
return ans + naj;
}
