#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);
for(int i = 0; i < m; i++) {
add(px[l[i]], py[i]);
add(px[r[i]], py[i]);
}
// nearest pole
/*{
vector<int> order(m);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j){return py[i] > py[j];});
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j){return h[i] > h[j];});
int cur = 0;
set<int> xs;
for(int i : order) {
while(cur < n && h[id[cur]] >= py[i]) {
xs.insert(px[id[cur]]);
cur++;
}
int L = px[l[i]], R = px[r[i]];
if(L < px[s] && px[s] < R) {
if(xs.find(px[s]) != xs.end()) add(px[s], py[i]);
else {
int u = *prev(xs.lower_bound(px[s]));
int v = *xs.upper_bound(px[s]);
add(u, py[i]); add(v, py[i]);
}
}
if(L < px[t] && px[t] < R) {
if(xs.find(px[t]) != xs.end()) add(px[t], py[i]);
else {
int u = *prev(xs.lower_bound(px[t]));
int v = *xs.upper_bound(px[t]);
add(u, py[i]); add(v, py[i]);
}
}
}
}*/
// nearest hor
/*{
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j){return h[i] > h[j];});
int cur = 0;
set<int> xs;
vector<pair<int, int>> pos;
for(auto i : p) pos.push_back(i);
sort(pos.begin(), pos.end(), [&](pair<int, int> i, pair<int, int> j){return i.second > j.second;});
for(auto it = pos.begin(); it != pos.end(); it++) {
int y = it->second;
while(cur < n && h[id[cur]] >= y) {
xs.insert(px[id[cur]]);
cur++;
}
auto i = xs.find(it->first);
assert(i != xs.end());
if(i != xs.begin()) add(*prev(i), y);
if(i != prev(xs.end())) add(*next(i), y);
}
}*/
// nearest ver
{
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);
}
//int cur = 0;
set<int> ys;
/*for(auto v : p) {
while(cur < n && px[cur] <= v.first) {
for(int i : rev[cur]) {
if(i < 0) {
ys.erase(py[~i]);
} else {
ys.insert(py[i]);
}
}
cur++;
}
auto it = ys.find(v.second);
if(it == ys.end()) continue;
if(it != ys.begin()) add(v.first, *prev(it));
if(it != prev(ys.end()) && *next(it) <= h[cur - 1]) add(v.first, *next(it));
}*/
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();
assert(sz <= 1500000);
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
int cnt = 0;
for(auto it = p.begin(); next(it) != p.end(); it++) {
if(it->first == next(it)->first) {
int u = cnt;
int v = cnt + 1;
int dis = abs(it->second - next(it)->second);
g[u].push_back({u, v, dis});
g[v].push_back({v, u, dis});
}
cnt++;
}
// add hor edge
map<int, vector<int>> Y;
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]];
for(int j = lower_bound(Y[y].begin(), Y[y].end(), L) - Y[y].begin(); Y[y][j] < R; 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]);
g[u].push_back({u, v, dis});
g[v].push_back({v, u, dis});
}
}
//
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];
}
