#include "walk.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define db(x) cerr << #x << ": " << (x) << '\n';
#define f first
#define s second
#define pb push_back
#define ii pair<int,int>
#define ll long long
#define maxn 1000010
#define inf 1000000007
#define INF 1000000000000000000ll
ll dp[maxn];
priority_queue<pair<ll,int>> q;
int n, m;
int st[maxn*4];
vector<ii> G[maxn];
set<ii> S;
map<ii,int> mp;
vector<pair<int,ii>> mp2;
void update(int nod,int l,int r,int id,int val){
if( l == r ){ st[nod] = val; return; }
int mi = ( l + r ) >> 1;
if( id <= mi ) update(2*nod,l,mi,id,val);
else update(2*nod+1,mi+1,r,id,val);
st[nod] = max( st[2*nod] , st[2*nod+1] );
}
int query(int nod,int l,int r,int x,int y,int val){
if( l > y || r < x || l > r ) return inf;
if( l == r ){
if( st[nod] >= val ) return l;
else return inf;
}
int mi = ( l + r ) >> 1;
if( l >= x && r <= y ){
if( st[2*nod] >= val ) return query(2*nod,l,mi,x,y,val);
if( st[2*nod+1] >= val ) return query(2*nod+1,mi+1,r,x,y,val);
return inf;
}
return min( query(2*nod,l,mi,x,y,val) , query(2*nod+1,mi+1,r,x,y,val) );
}
void dijkstra(int start,int end_){
fill( dp , dp + maxn , INF );
q.push({0,start});
dp[start] = 0;
while( !q.empty() ){
int u = q.top().s;
if( dp[u] < -q.top().f ){ q.pop(); continue; }
q.pop();
if( u == end_ ) return;
for( auto v : G[u] ){
if( dp[v.f] > dp[u] + v.s ){
dp[v.f] = dp[u] + v.s;
q.push({-dp[v.f],v.f});
}
}
}
}
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) {
n = x.size();
m = y.size();
for(int i=0; i<n; i++){
update(1,0,n-1,i,h[i]);
S.insert((ii){x[i],h[i]});
S.insert((ii){x[i],0});
}
for(int i=0; i<m; i++){
int tl = l[i], tr = r[i];
while( tl <= tr ){
int p = query(1,0,n-1,tl,tr,y[i]);
if( p == inf ) break;
S.insert({x[p],y[i]});
if( p > tl - 1 && tl - 1 >= l[i] ){ mp2.pb({y[i],{x[tl-1],x[p]}}); }
tl = p + 1;
}
}
int cnt = 0;
for( auto i : S ){
//S2.insert({i.s,i.f});
mp[{i.f,i.s}] = ++cnt;
}
for( auto i : S ){
auto it = S.upper_bound(i);
if( it == S.end() ) continue;
ii j = *it;
if( i.f == j.f ){
int u = mp[i];
int v = mp[j];
G[u].pb({v,abs(j.s-i.s)});
G[v].pb({u,abs(j.s-i.s)});
}
}
for( auto i : mp2 ){
int uf = i.s.f;
int vf = i.s.s;
int us = i.f;
int u = mp[{uf,us}];
int v = mp[{vf,us}];
G[u].pb({v,abs(uf-vf)});
G[v].pb({u,abs(uf-vf)});
}
dijkstra(mp[{x[s],0}],mp[{x[g],0}]);
if( dp[mp[{x[g],0}]] == INF ) return -1;
return dp[mp[{x[g],0}]];
}
