#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define _all(T) T.begin(),T.end()
#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#define pll pair<ll,ll>
const int mxn = 2e6+10;
const ll inf = 1e18;
vector<pii> paths[mxn];
ll dist[mxn];
int N;
vector<pii> pts;
set<int> st;
vector<pii> op;
namespace DIJKSTRA{
priority_queue<pll,vector<pll>,greater<pll>> pq;
bitset<mxn> vis;
void GO(){
vis.reset();
for(int i = 0;i<pts.size();i++)pq.push(pll(dist[i],i));
while(!pq.empty()){
auto [d,now] = pq.top();
pq.pop();
if(vis[now])continue;
vis[now] = true;
for(auto [nxt,w]:paths[now]){
if(vis[nxt]||d+w>=dist[nxt])continue;
dist[nxt] = d+w;
pq.push(pll(d+w,nxt));
}
}
return;
}
}
long long min_distance(std::vector<int32_t> x, std::vector<int32_t> H, std::vector<int32_t> l, std::vector<int32_t> r, std::vector<int32_t> y, int32_t s, int32_t ed) {
N = x.size();
for(int i = 0;i<N;i++){
op.push_back(pii(H[i],i));
}
for(int i = 0;i<l.size();i++){
op.push_back(pii(y[i],-i-1));
}
sort(op.rbegin(),op.rend());
for(auto [h,id]:op){
if(id>=0){
pts.push_back(pii(id,h));
st.insert(id);
}
else{
id = -id;
id--;
auto lit = st.lower_bound(l[id]);
auto rit = st.upper_bound(r[id]);
for(auto it = lit;it != rit;it++){
pts.push_back(pii(*it,h));
}
id = -id;
}
}
for(int i = 0;i<N;i++)pts.push_back(pii(i,0));
sort(pts.begin(),pts.end());
pts.resize(unique(pts.begin(),pts.end())-pts.begin());
st.clear();
for(auto [h,id]:op){
if(id>=0){
st.insert(id);
}
else{
id = -id;
id--;
auto lit = st.find(l[id]);
auto rit = st.upper_bound(r[id]);
int pre = lower_bound(_all(pts),pii(*lit,h))-pts.begin();
for(auto it = lit;it != rit;it++){
int now = lower_bound(_all(pts),pii(*it,h))-pts.begin();
if(it != lit){
paths[now].push_back(pii(pre,x[*it]-x[*prev(it)]));
paths[pre].push_back(pii(now,x[*it]-x[*prev(it)]));
}
pre = now;
}
}
}
for(int i = 1;i<pts.size();i++){
if(pts[i].fs == pts[i-1].fs){
paths[i].push_back(pii(i-1,pts[i].sc-pts[i-1].sc));
paths[i-1].push_back(pii(i,pts[i].sc-pts[i-1].sc));
}
}
fill(dist,dist+pts.size(),inf);
s = lower_bound(pts.begin(),pts.end(),pii(s,0))-pts.begin();
ed = lower_bound(pts.begin(),pts.end(),pii(ed,0))-pts.begin();
dist[s] = 0;
DIJKSTRA::GO();
ll ans = dist[ed];
return ans>=inf?-1:ans;
}
