#pragma GCC optimize("O3")
#include "walk.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
const ll inf=(ll)2e18;
const ll mxn=2e5+5;
struct segtree{
vector<multiset<ll>> st;
segtree(){
st.resize(mxn*4);
}
void update(ll pos,ll val,ll d,ll l=0,ll r=mxn-1,ll v=1){
if(d==1) st[v].insert(val);
else st[v].erase(st[v].find(val));
if(l==r){
return;
}
ll mid=(l+r)/2;
if(pos<=mid) update(pos,val,d,l,mid,v*2);
else update(pos,val,d,mid+1,r,v*2+1);
}
ll query(ll tl,ll tr,ll l=0,ll r=mxn-1,ll v=1){
if(r<tl or tr<l){
return inf;
}
if(tl<=l and r<=tr){
if(st[v].empty()) return inf;
else return *st[v].begin();
}
ll mid=(l+r)/2;
return min(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
}
};
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
ll n=(ll)x.size();
ll m=(ll)l.size();
vector<ll> ys;
ys.push_back(0);
for(ll i=0;i<n;i++){
ys.push_back(h[i]);
}
for(ll i=0;i<m;i++){
ys.push_back(y[i]);
}
sort(all(ys));
ys.resize(unique(all(ys))-ys.begin());
vector<vector<ll>> st(n),en(n);
for(ll i=0;i<m;i++){
st[r[i]].push_back(i);
en[l[i]].push_back(i);
}
segtree st1,st2;
vector<ll> dp(m);
vector<ll> v1(m),v2(m);
st1.update(0,0,1);
ll ans;
set<pair<int,int>> S;
for(ll i=n-1;i>=0;i--){
ll up=lower_bound(all(ys),h[i])-ys.begin();
for(auto v:st[i]){
ll pos=lower_bound(all(ys),y[v])-ys.begin();
dp[v]=inf;
dp[v]=min(dp[v],st1.query(0,pos)+y[v]);
dp[v]=min(dp[v],st2.query(pos,up)-y[v]);
//cout<<v+1<<' '<<pos<<' '<<up<<' '<<dp[v]<<'\n';
}
for(auto v:st[i]){
ll pos=lower_bound(all(ys),y[v])-ys.begin();
//cout<<"+ "<<pos<<' '<<v<<'\n';
st1.update(pos,dp[v]-y[v],1);
st2.update(pos,dp[v]+y[v],1);
v1[v]=dp[v]-y[v];
v2[v]=dp[v]+y[v];
S.insert({y[v],v});
}
if(i==0){
ans=st2.query(0,up)+x[n-1]-x[0];
}
if(i==n-1) st1.update(0,0,0);
for(auto v:en[i]){
ll pos=lower_bound(all(ys),y[v])-ys.begin();
//cout<<"- "<<pos<<' '<<v<<'\n';
st1.update(pos,v1[v],0);
st2.update(pos,v2[v],0);
S.erase({y[v],v});
auto it=S.lower_bound({y[v]+1,0});
if(S.empty() or it==S.begin()) continue;
it--;
int u=(*it).s;
if(v1[v]+(y[v]-y[u])*2<v1[u]){
ll pos2=lower_bound(all(ys),y[u])-ys.begin();
st1.update(pos2,v1[u],0);
v1[u]=v1[v]+(y[v]-y[u])*2;
st1.update(pos2,v1[u],1);
}
if(v2[v]<v2[u]){
ll pos2=lower_bound(all(ys),y[u])-ys.begin();
st2.update(pos2,v2[u],0);
v2[u]=v2[v];
st2.update(pos2,v2[u],1);
}
}
}
return (ans>=(ll)1e18?-1:ans);
}
