#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;
set <pair<int, ll> > s2;
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] + 1].push_back(y[i]);
}
for(int i = 0; i < poc[0].size(); i++){
int vis = poc[0][i];
s.insert({vis, vis});
}
for(int i = 1; i < n; i++){
if(s.empty()) return -1;
for(int j = 0; j < poc[i].size(); j++){
int vis = poc[i][j];
ll cost = inf;
auto it = s.lower_bound({vis, 0});
if(it != s.end()) cost = (*it).se + (*it).fi - vis;
if(it != s.begin()){
it--;
cost = min(cost, (*it).se + vis - (*it).fi);
}
s.insert({vis, cost});
}
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;
it++;
if(it != s.end()){
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++;
}
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;
}
