#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 t;
int dis;
edge(int _t, int _dis) : t(_t), dis(_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;
}
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
public:
int n;
vector<vector<T>> mat;
F func;
SparseTable(const vector<T>& a, const F& f) : func(f) {
n = static_cast<int>(a.size());
int max_log = 32 - __builtin_clz(n);
mat.resize(max_log);
mat[0] = a;
for (int j = 1; j < max_log; j++) {
mat[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++) {
mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
}
}
}
T get(int from, int to) const {
assert(0 <= from && from <= to && to <= n - 1);
int lg = 32 - __builtin_clz(to - from + 1) - 1;
return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
}
};
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]);
}
//
SparseTable<int> d(h, [&](int i, int j){return max(i, j);});
auto find_left = [&](int l, int r, int y) {
if(d.get(l, r) < y) return -1;
while(r - l >= 1) {
int mid = (r + l) >> 1;
if(d.get(l, mid) < y) l = mid + 1;
else r = mid;
}
return r;
};
auto find_right = [&](int l, int r, int y) {
if(d.get(l, r) < y) return -1;
while(r - l >= 1) {
int mid = (r + l) >> 1;
if(d.get(mid + 1, r) < y) r = mid;
else l = mid + 1;
}
return r;
};
//near pole
/*for(int i = 0; i < m; i++) {
int y = py[i];
for(int rot = 0; rot < 2; rot++) {
if(l[i] < s && s < r[i]) {
int ll = find_right(l[i], s, y);
int rr = find_left(s, r[i], y);
if(ll != -1) add(px[ll], y);
if(rr != -1) add(px[rr], y);
}
swap(s, t);
}
}*/
vector<pair<int, int>> ad;
// near ver
/*{
for(auto pp : p) {
int x = pp.first, y = pp.second;
int id = lower_bound(px.begin(), px.end(), x) - px.begin();
if(id < n - 1) {
int ll = find_left(id + 1, n - 1, y);
if(ll != -1) ad.emplace_back(px[ll], y);
}
if(id > 0) {
int rr = find_right(0, id - 1, y);
if(rr != -1) ad.emplace_back(px[rr], y);
}
}
}*/
{
vector<vector<int>> inc(n);
vector<vector<int>> rev(n);
for(int i = 0; i < m; i++) {
inc[l[i]].push_back(i);
if(r[i] < n - 1) rev[r[i] + 1].push_back(i);
}
int cur = 0;
map<int, int> Y;
for(auto pp : p) {
int x = pp.first, y = pp.second;
while(cur < n && px[cur] <= x) {
for(int i : rev[cur]) {
Y[py[i]]--;
if(Y[py[i]] == 0) Y.erase(py[i]);
}
for(int i : inc[cur]) Y[py[i]]++;
cur++;
}
for(auto i : Y) if(i.first <= h[cur - 1]) ad.emplace_back(x, i.first);
/*auto it = Y.find(y);
if(it == Y.end()) continue;
if(it != Y.begin()) ad.emplace_back(x, prev(it)->first);
if(it != prev(Y.end())) ad.emplace_back(x, next(it)->first);*/
}
}
for(auto i : ad) add(i.first, i.second);
//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
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].emplace_back(v, dis);
g[v].emplace_back(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].emplace_back(v, dis);
g[v].emplace_back(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];
}
