#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int min_distance(vector<signed> x, vector<signed> h, vector<signed> l, vector<signed> r, vector<signed> y, signed start, signed end){
vector<vector<pii> > graph(max(y.size(), x.size())*10), vect(x.size());
vector<pii> ooga(h.size()), booga(y.size());
for (int i=0; i<h.size(); ++i)ooga[i]=mp(h[i], i);
for (int i=0; i<y.size(); ++i)booga[i]=mp(y[i], i);
sort(ooga.begin(), ooga.end(), greater<pii>());
sort(booga.begin(), booga.end(), greater<pii>());
set<int> s;
int p=0, counter=0;
for (auto c:booga){
if (r[c.se]<=start||start<=l[c.se])continue;
while (p<h.size()&&ooga[p].fi>=c.fi)s.insert(ooga[p].se), ++p;
int a=*(--s.upper_bound(start)), b=*s.lower_bound(start);
l.pb(l[c.se]), r.pb(a), y.pb(c.fi);
l.pb(a), r.pb(b), y.pb(c.fi);
l.pb(b), r.pb(r[c.se]), y.pb(c.fi);
a=*(--s.upper_bound(end)), b=*s.lower_bound(end);
l.pb(l[c.se]), r.pb(a), y.pb(c.fi);
l.pb(a), r.pb(b), y.pb(c.fi);
l.pb(b), r.pb(r[c.se]), y.pb(c.fi);
}
s.clear();
booga.clear();
for (int i=0; i<y.size(); ++i)booga[i]=mp(y[i], i);
sort(booga.begin(), booga.end(), greater<pii>());
p=0;
for (auto c:booga){
while (p<h.size()&&ooga[p].fi>=c.fi)s.insert(ooga[p].se), ++p;
int a=l[c.se], b=r[c.se];
s.insert(a);
s.insert(b);
int prev=-1;
vector<int> del;
for (auto it=s.lower_bound(a); it!=s.end()&&*it<=b; ++it){
if (vect[*it].size()){
graph[vect[*it].back().se].pb(mp(counter, vect[*it].back().fi-c.fi));
graph[counter].pb(mp(vect[*it].back().se, vect[*it].back().fi-c.fi));
}
vect[*it].pb(mp(c.fi, counter));
if (prev!=-1){
graph[counter-1].pb(mp(counter, x[*it]-x[prev]));
graph[counter].pb(mp(counter-1, x[*it]-x[prev]));
}
prev=*it;
++counter;
if (*it!=a&&*it!=b)del.pb(*it);
}
for (auto a:del)s.erase(a);
}
if (vect[start].size()){
graph[vect[start].back().se].pb(mp(counter, vect[start].back().fi));
graph[counter].pb(mp(vect[start].back().se, vect[start].back().fi));
}
++counter;
if (vect[end].size()){
graph[vect[end].back().se].pb(mp(counter, vect[end].back().fi));
graph[counter].pb(mp(vect[end].back().se, vect[end].back().fi));
}
++counter;
vector<int> dist(counter, LLONG_MAX/2);
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push(mp(0, counter-2));
while (pq.size()){
int node=pq.top().se, d=pq.top().fi;
pq.pop();
if (d>=dist[node])continue;
dist[node]=d;
for (auto num:graph[node])pq.push(mp(d+num.se, num.fi));
}
return (dist[counter-1]==LLONG_MAX/2?-1:dist[counter-1]);
}
