#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 1e18;
const ll lim = 1e9;
struct pos{
ll x,y;
bool operator<(const pos &o) const{
return x!=o.x?x<o.x:y<o.y;
}
bool operator==(const pos &o) const{
return x==o.x&&y==o.y;
}
bool operator!=(const pos &o) const{
return x!=o.x||y!=o.y;
}
};
struct line{
ll i,v;
bool operator<(const line &o) const{
return v>o.v;
}
};
struct obj{
ll l,r,y;
bool operator<(const obj &o) const{
return l<o.l;
}
};
struct nod{
ll l,r,lv,rv;
nod operator+(const nod &o) const{
return {l,o.r,min(lv,o.lv+o.l-l),min(rv+o.r-r,o.rv)};
}
};
struct segtree{
ll n;
vector<nod> a;
vector<ll> xs;
segtree(const vector<ll> &XS):n(XS.size()),a(XS.size()*4),xs(XS){
//cerr << "size=" << n << "\n";
init(1,0,n-1);
}
void init(ll i, ll l, ll r){
if (l==r) a[i] = {xs[l],xs[l],big,big};
else{
ll m = l+r>>1;
init(i<<1,l,m);
init(i<<1|1,m+1,r);
a[i] = a[i<<1]+a[i<<1|1];
}
}
void mod(ll i, ll l, ll r, ll x, ll v){
if (l==r) a[i].lv = a[i].rv = v;
else{
ll m = l+r>>1;
if (x<=m) mod(i<<1,l,m,x,v);
else mod(i<<1|1,m+1,r,x,v);
a[i] = a[i<<1]+a[i<<1|1];
}
}
void mod(ll x, ll v){
ll idx = lower_bound(xs.begin(),xs.end(),x)-xs.begin();
mod(1,0,n-1,idx,v);
}
nod get(ll i, ll l, ll r, ll ql, ll qr){
if (ql<=l&&r<=qr) return a[i];
else{
ll m = l+r>>1;
if(qr<=m) return get(i<<1,l,m,ql,qr);
else if(ql>m) return get(i<<1|1,m+1,r,ql,qr);
else return get(i<<1,l,m,ql,qr)+get(i<<1|1,m+1,r,ql,qr);
}
}
ll qry(ll x){
ll idx = lower_bound(xs.begin(),xs.end(),x)-xs.begin();
return min(get(1,0,n-1,0,idx).rv,get(1,0,n-1,idx,n-1).lv);
}
};
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) {
ll n = x.size();
ll m = y.size();
if (s==0&&g==n-1){
//cerr << "special fork\n";
deque<obj> bs;
for(ll i = 0;i<m;i++){
bs.push_back({x[l[i]],x[r[i]],y[i]});
}
sort(bs.begin(),bs.end());
//cerr << "cp1\n";
vector<ll> ys(1,0);
for(ll i = 0;i<n;i++) ys.push_back(h[i]);
for(ll i = 0;i<m;i++) ys.push_back(y[i]);
//cerr << "cp2\n";
sort(ys.begin(),ys.end());
ys.erase(unique(ys.begin(),ys.end()),ys.end());
//cerr << "cp3\n";
//cerr << ys.size() << "\n";
segtree t(ys);
//cerr << "cp4\n";
t.mod(0,0);
deque<pair<ll,ll>> exp;
//cerr << "cp5\n";
exp.push_back({x[0],0});
ll ans = big;
//cerr << "cp6\n";
for(ll i : x){
vector<pair<ll,ll>> upd;
while(bs.size()&&bs.front().l<=i){
obj o = bs.front();bs.pop_front();
ll val = t.qry(o.y);
//cerr << val << "\n";
upd.push_back({o.y,val});
exp.push_back({o.r,o.y});
}
if (i==x.back()){
ll ans = t.qry(0)+x.back()-x.front();
if (ans>=big) ans = -1;
return ans;
}
while(exp.size()&&exp.front().first<=i){
auto o = exp.front();exp.pop_front();
t.mod(o.second,big);
}
for(auto o : upd){
t.mod(o.first,o.second);
}
}
}
vector<pos> ps;
for(ll i = 0;i<n;i++) ps.push_back({x[i],0});
{
vector<pair<ll,ll>> builds,bridges;
for(ll i = 0;i<n;i++) builds.push_back({h[i],i});
for(ll i = 0;i<m;i++) bridges.push_back({y[i],i});
sort(builds.begin(),builds.end());
sort(bridges.rbegin(),bridges.rend());
set<ll> s;
for(auto [yy,i] : bridges){
while(builds.size()&&(builds.back().first)>=yy){
s.insert(builds.back().second);
////cerr << "add build " << builds.back().second << "\n";
builds.pop_back();
}
for(auto it = s.lower_bound(l[i]);it!=s.end()&&(*it)<=r[i];it++){
////cerr << "add " << x[*it] << ", " << y[i] << "\n";
ps.push_back({x[*it],y[i]});
}
}
}
/*for(ll i = 0;i<m;i++){
for(ll j = l[i];j<=r[i];j++){
if (h[j]>=y[i]){
ps.push_back({x[j],y[i]});
}
}
}*/
sort(ps.begin(),ps.end());
ps.erase(unique(ps.begin(),ps.end()),ps.end());
auto gp = [&](pos p){
return lower_bound(ps.begin(),ps.end(),p)-ps.begin();
};
ll c = ps.size();
vector<vector<line>> con(c);
for(ll i = 1;i<c;i++){
if (ps[i-1].x==ps[i].x){
ll d = ps[i].y-ps[i-1].y;
con[i-1].push_back({i,d});
con[i].push_back({i-1,d});
}
}
{
vector<pair<ll,ll>> builds,bridges;
for(ll i = 0;i<n;i++) builds.push_back({h[i],i});
for(ll i = 0;i<m;i++) bridges.push_back({y[i],i});
sort(builds.begin(),builds.end());
sort(bridges.rbegin(),bridges.rend());
set<ll> s;
for(auto [yy,i] : bridges){
vector<ll> v;
while(builds.size()&&(builds.back().first)>=yy){
s.insert(builds.back().second);
////cerr << "add build " << builds.back().second << "\n";
builds.pop_back();
}
for(auto it = s.lower_bound(l[i]);it!=s.end()&&(*it)<=r[i];it++){
////cerr << "add " << x[*it] << ", " << y[i] << "\n";
v.push_back(gp({x[*it],y[i]}));
}
for(ll j = 1;j<v.size();j++){
ll d = ps[v[j]].x-ps[v[j-1]].x;
con[v[j-1]].push_back({v[j],d});
con[v[j]].push_back({v[j-1],d});
}
}
}
/*for(ll i = 0;i<m;i++){
vector<ll> v;
for(ll j = l[i];j<=r[i];j++){
if (h[j]>=y[i]){
v.push_back(gp({x[j],y[i]}));
}
}
for(ll j = 1;j<v.size();j++){
ll d = ps[v[j]].x-ps[v[j-1]].x;
con[v[j-1]].push_back({v[j],d});
con[v[j]].push_back({v[j-1],d});
}
}*/
ll start = gp({x[s],0});
ll goal = gp({x[g],0});
vector<ll> dis(c,big);
priority_queue<line> q;
q.push({start,0});
while(q.size()){
auto [i,v] = q.top();q.pop();
if(dis[i]<=v) continue;
dis[i] = v;
for(auto [j,w] : con[i]){
q.push({j,v+w});
}
}
ll ans = dis[goal];
if (ans>=big) ans = -1;
return ans;
}
