#include "walk.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
const ll INFL=0x3f3f3f3f3f3f3f3f;
struct st{
int l,r,y;
};
static map<P,int>mp;
static ll d[2000000];
static int cnt=0;
static vector<P>E[2000000];
void add_edge(P a,P b,int dist){
if(!mp.count(a)){
mp[a]=cnt++;
}
if(!mp.count(b)){
mp[b]=cnt++;
}
E[mp[a]].push_back(P(dist,mp[b]));
E[mp[b]].push_back(P(dist,mp[a]));
}
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=x.size();
int m=l.size();
mp.clear();
cnt=0;
rep(i,n)E[i].clear();
vector<st>H;
rep(i,m){
H.push_back({l[i],r[i],y[i]});
}
sort(H.begin(),H.end(),[](st a,st b){return a.y>b.y;});
vector<P>V;
rep(i,n){
V.push_back(P(h[i],i));
}
sort(V.begin(),V.end(),[](P a,P b){return a.first>b.first;});
set<int>se;
int cur=0;
for(auto&p:H){
while(cur<V.size()&&V[cur].first>=p.y){
se.insert(V[cur].second);
cur++;
}
auto it=se.lower_bound(p.l);
while(it!=se.end()&&*it<p.r){
int L=*it;
it++;
int R=*it;
add_edge(P(L,p.y),P(R,p.y),x[R]-x[L]);
}
}
map<int,vector<int>>mp_v;
mp_v[s].push_back(0);
mp_v[g].push_back(0);
for(auto&p:mp){
mp_v[p.first.first].push_back(p.first.second);
}
for(auto&v:mp_v){
rep(i,v.second.size()-1){
add_edge(P(v.first,v.second[i]),P(v.first,v.second[i+1]),v.second[i+1]-v.second[i]);
}
}
priority_queue<P,vector<P>,greater<P>>que;
memset(d,0x3f,sizeof(d));
d[mp[P(s,0)]]=0;
que.push(P(0,mp[P(s,0)]));
while(!que.empty()){
P p=que.top();que.pop();
if(d[p.second]!=p.first)continue;
for(P&u:E[p.second]){
if(d[u.second]>p.first+u.first){
d[u.second]=p.first+u.first;
que.push(P(d[u.second],u.second));
}
}
}
ll ans=d[mp[P(g,0)]];
if(ans==INFL)return -1;
return ans;
}
