#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);
struct edge {
int f;
int t;
int dis;
};
vector<long long> calc(int n, int s, int t, vector<vector<edge>> g) {
vector<long long> ret(n, LLONG_MAX);
ret[s] = 0;
set<pair<long long, int>> que;
vector<int> was(n);
que.insert({ret[s], s});
while(que.size()) {
int v = que.begin()->second;
que.erase(que.begin());
if(was[v]) continue;
was[v] = 1;
for(edge e : g[v]) {
int u = e.t;
if(ret[u] > ret[v] + e.dis) {
ret[u] = ret[v] + e.dis;
que.insert(make_pair(ret[u], u));
}
}
}
return ret;
}
long long min_distance(vector<int> px, vector<int> h, vector<int> l, vector<int> r, vector<int> py, int s, int t) {
int n = px.size();
int m = py.size();
set<pair<int, int>> p;
auto add = [&](int x, int y) {
p.insert(make_pair(x, y));
};
add(px[s], 0);
add(px[t], 0);
{
vector<vector<int>> rev(n);
for(int i = 0; i < m; i++) {
rev[l[i]].push_back(i);
if(r[i] < n - 1) rev[r[i] + 1].push_back(~i);
}
set<int> ys;
for(int cur = 0; cur < n; cur++) {
for(int i : rev[cur]) {
if(i < 0) {
ys.erase(py[~i]);
} else {
ys.insert(py[i]);
}
}
for(int j : ys) {
if(j > h[cur]) break;
add(px[cur], j);
}
}
}
//numerate
int sz = p.size();
map<pair<int, int>, int> id;
for(auto i : p) {
int fp = id.size();
id[i] = fp;
}
vector<vector<edge>> g(sz);
// add ver edged
for(auto it = p.begin(); next(it) != p.end(); it++) {
if(it->first == next(it)->first) {
int u = id[*it];
int v = id[*next(it)];
int dis = abs(it->second - next(it)->second);
g[u].push_back({u, v, dis});
g[v].push_back({v, u, dis});
}
}
// add hor edge
map<int, vector<int>> Y;
long long bug = 0;
for(auto i : p) Y[i.second].push_back(i.first);
for(int i = 0; i < m; i++) {
int y = py[i];
int L = px[l[i]];
int R = px[r[i]];
bug -= R - L;
int st = lower_bound(Y[y].begin(), Y[y].end(), L) - Y[y].begin();
int fin = lower_bound(Y[y].begin(), Y[y].end(), R) - Y[y].begin();
assert(0 <= st && st <= fin && fin < Y[y].size());
assert(Y[y][st] == L);
assert(Y[y][fin] == R);
for(int j = st; j < fin; j++) {
int u = id[make_pair(Y[y][j], y)];
int v = id[make_pair(Y[y][j + 1], y)];
int dis = abs(Y[y][j] - Y[y][j + 1]);
bug += dis;
g[u].push_back({u, v, dis});
g[v].push_back({v, u, dis});
}
}
assert(bug == 0);
//
int ss = id[make_pair(px[s], 0)];
int tt = id[make_pair(px[t], 0)];
vector<long long> ret = calc(sz, ss, tt, g);
if(ret[tt] == LLONG_MAX) return -1;
return ret[tt];
}
/*int main() {
cout << min_distance({0, 3, 5, 7, 10, 12, 14},
{8, 7, 9, 7, 6, 6, 9},
{0, 0, 0, 2, 2, 3, 4},
{1, 2, 6, 3, 6, 4, 6},
{1, 6, 8, 1, 7, 2, 5},
1, 5);
return 0;
}*/
