#include "walk.h"
#include<bits/stdc++.h>
#define ll long long
#define sz(v) (int)(v.size())
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int inf=1e9+7;
const ll INF=1e16;
struct node{
ll s1, resp, s2;
};
class SparseSeg{
protected:
vector<node>seg;
vector<int> e, d;
public:
int cria(){
seg.push_back({INF,INF,INF});
e.push_back(0);
d.push_back(0);
return sz(seg)-1;
}
SparseSeg() { cria(); cria();}
int getLeft(int id){
if(e[id]) return e[id];
return e[id]=cria();
}
int getRight(int id){
if(d[id]) return d[id];
return d[id]=cria();
}
node merge(node e, node d){
node ret;
ret.s1=min(e.s1,d.s1); ret.resp=min(e.resp,d.resp); ret.s2=min(e.s2,d.s2);
return ret;
}
void update(int id, ll ini, ll fim, int cara, ll val){
if(ini==fim){
seg[id].s1=val-ini;
seg[id].s2=val+ini;
seg[id].resp=val;
return;
}
int mid=(ini+fim)/2;
if(cara<=mid) update(getLeft(id),ini,mid,cara,val);
else update(getRight(id),mid+1,fim,cara,val);
seg[id]=merge(seg[e[id]],seg[d[id]]);
}
node query(int id, ll ini, ll fim, int l, int r){
if(ini>r||fim<l) return seg[0];
if(l<=ini&&fim<=r) return seg[id];
int mid=(ini+fim)/2;
return merge(query(e[id],ini,mid,l,r),query(d[id],mid+1,fim,l,r));
}
};
SparseSeg ds;
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
int n=sz(x), m=sz(l);
vector<vector<pii>>v(n);
for(int i=0;i<m;i++) v[l[i]].push_back({y[i],r[i]});
set<pii>ends;
ends.insert({0,0});
ds.update(1,0,inf,0,0);
map<int,int>mp;
for(int i=0;i<n-1;i++){
for(pii p : v[i]){
if(mp[p.fi]>=i&&i){
if(mp[p.fi]<p.se){
ends.erase({mp[p.fi],p.fi});
mp[p.fi]=p.se;
ends.insert({mp[p.fi],p.fi});
}
}else{
node l=ds.query(1,0,inf,0,p.fi-1), r=ds.query(1,0,inf,p.fi+1,inf);
ll cost=min(l.s1+p.fi,r.s2-p.fi);
// cout << i << ' ' << p.se << ' ' << p.fi << ' ' << cost << '\n';
if(cost<INF){
ds.update(1,0,inf,p.fi,cost);
mp[p.fi]=p.se;
ends.insert({mp[p.fi],p.fi});
}
}
}
while(sz(ends)){
auto f=ends.begin();
int u=f->first;
if(u>i) break;
int z=f->second;
ends.erase(f);
ds.update(1,0,inf,z,INF);
}
}
if(ds.query(1,0,inf,0,inf).s2>=INF) return -1;
ll add=x.back()-x[0];
return ds.query(1,0,inf,0,inf).s2+add;
}
