//#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 int mxn=2e5+5;
struct segtree{
vector<multiset<int>> st;
segtree(){
st.resize(mxn*4);
}
void update(int pos,ll val,int d,int l=0,int r=mxn-1,int v=1){
if(d==1) st[v].insert(val);
else st[v].erase(st[v].find(val));
if(l==r){
return;
}
int 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(int tl,int tr,int l=0,int r=mxn-1,int 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();
}
int 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) {
int n=(int)x.size();
int m=(int)l.size();
vector<int> ys;
ys.push_back(0);
for(int i=0;i<n;i++){
ys.push_back(h[i]);
}
for(int i=0;i<m;i++){
ys.push_back(y[i]);
}
sort(all(ys));
ys.resize(unique(all(ys))-ys.begin());
vector<vector<int>> st(n),en(n);
for(int i=0;i<m;i++){
st[r[i]].push_back(i);
en[l[i]].push_back(i);
}
segtree st1,st2;
vector<ll> dp(m);
st1.update(0,x[n-1],1);
ll ans;
for(int i=n-1;i>=0;i--){
int up=lower_bound(all(ys),h[i])-ys.begin();
for(auto v:st[i]){
int pos=lower_bound(all(ys),y[v])-ys.begin();
dp[v]=inf;
dp[v]=min(dp[v],st1.query(0,pos)-x[i]+y[v]);
dp[v]=min(dp[v],st2.query(pos,up)-x[i]-y[v]);
st1.update(pos,dp[v]+x[i]-y[v],1);
st2.update(pos,dp[v]+x[i]+y[v],1);
}
if(i==0){
ans=st2.query(0,up)-x[0];
}
if(i==n-1) st1.update(0,x[n-1],0);
for(auto v:en[i]){
int pos=lower_bound(all(ys),y[v])-ys.begin();
st1.update(pos,dp[v]+x[r[v]]-y[v],0);
st2.update(pos,dp[v]+x[r[v]]+y[v],0);
}
}
return (ans>=(ll)1e18?-1:ans);
}
