#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple0
#define x first
#define y second
#include "walk.h"
namespace my {
const int T = 1 << 17;
const int N = 1 << 20;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3fLL;
const int NONE = -19;
struct str_1 {
str_1() {
fill_n(ass, 2 * T, NONE);
}
int ass[2 * T];
int ls(int v) {
return 2 * v + 1;
}
int rs(int v) {
return 2 * v + 2;
}
void push(int v) {
if (ass[v] == NONE) {
return;
}
ass[ls(v)] = ass[rs(v)] = ass[v];
ass[v] = NONE;
}
void upd(int v, int vl, int vr, int ql, int qr, int val) {
if (ql <= vl && vr <= qr) {
ass[v] = val;
return;
}
if (qr <= vl || vr <= ql) {
return;
}
int vm = (vl + vr) / 2;
push(v);
upd(ls(v), vl, vm, ql, qr, val);
upd(rs(v), vm, vr, ql, qr, val);
}
void upd(int l, int r, int v) {
// for (int i = l; i <= r; ++i) {
// arr[i] = v;
// }
upd(0, 0, T, l, r + 1, v);
}
int query(int v, int vl, int vr, int pos) {
assert(vl <= pos && pos < vr);
if (vr - vl == 1) {
return ass[v];
}
int vm = (vl + vr) / 2;
push(v);
if (pos < vm) {
return query(ls(v), vl, vm, pos);
} else {
return query(rs(v), vm, vr, pos);
}
}
int query(int i) {
// return arr[i];
return query(0, 0, T, i);
}
} assigner;
struct str_2 {
int arr[N];
void upd(int i, int v) {
arr[i] = v;
}
int to_rig(int i, int v) {
while (i < N && arr[i] < v) {
++i;
}
return i;
}
int to_lef(int i, int v) {
while (i >= 0 && arr[i] < v) {
--i;
}
return i;
}
} gfinder;
struct walk {
int l, r, y, i;
walk(int a, int b, int c) : l(a), r(b), y(c), i(-1) {}
};
bool operator<(walk a, walk b) {
return a.y < b.y;
}
vector<walk> was;
vector<int> ord[N];
vector<pair<int, int>> pt;
map<pair<int, int>, int> ma;
vector<pair<int, int>> g[N];
ll dist[N];
int _get_id(int x, int y) {
auto p = make_pair(x, y);
if (ma.count(p)) {
return ma[p];
} else {
int v = (int)ma.size();
assert((int)pt.size() < N);
pt.emplace_back(x, y);
return ma[p] = v;
}
// int i = (int)(find(all(pt), mp(x, y)) - pt.begin());
// return i;
}
int get_id(int x, int y) {
int i = _get_id(x, y);
assert(pt[i].x == x);
assert(pt[i].y == y);
return i;
}
void add_edge(int v, int u) {
assert(pt[v].x == pt[u].x || pt[v].y == pt[u].y);
if (v == u) {
return;
}
// cout << "edge " << v << " " << u << endl;
int w = abs(pt[v].x - pt[u].x) + abs(pt[v].y - pt[u].y);
// cout << "edge " << pt[v].x << " " << pt[v].y << " " << pt[u].x << " " << pt[u].y << " " << w << endl;
g[v].emplace_back(u, w);
g[u].emplace_back(v, w);
}
void vert_edge(int x, int i, int j) {
assert(i != -1);
// cout << "vert " << x << " " << i << " " << j << endl;
if (j == -1) {
int v = get_id(x, was[i].y);
ord[i].push_back(v);
return;
}
int v = get_id(x, was[i].y);
int u = get_id(x, was[j].y);
ord[i].emplace_back(v);
ord[j].emplace_back(u);
add_edge(v, u);
}
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int st, int fi) {
using namespace my;
int n = (int)x.size(), m = (int)l.size();
for (int i = 0; i < n; ++i) {
gfinder.upd(i, h[i]);
}
vector<walk> temp;
for (int i = 0; i < m; ++i) {
was.emplace_back(l[i], r[i], y[i]);
}
was.emplace_back(0, n - 1, 0);
sort(all(was));
for (auto e : was) {
if (e.l <= st && st <= e.r) {
int a = gfinder.to_lef(st, e.y);
int b = gfinder.to_rig(st, e.y);
assert(e.l <= a && a <= b && b <= e.r);
if (e.l < a) {
temp.emplace_back(e.l, a, e.y);
}
if (a < b) {
temp.emplace_back(a, b, e.y);
}
if (b < e.r) {
temp.emplace_back(b, e.r, e.y);
}
} else {
temp.push_back(e);
}
}
was = temp;
temp.clear();
for (auto e : was) {
if (e.l <= fi && fi <= e.r) {
int a = gfinder.to_lef(fi, e.y);
int b = gfinder.to_rig(fi, e.y);
assert(e.l <= a && a <= b && b <= e.r);
if (e.l < a) {
temp.emplace_back(e.l, a, e.y);
}
if (a < b) {
temp.emplace_back(a, b, e.y);
}
if (b < e.r) {
temp.emplace_back(b, e.r, e.y);
}
} else {
temp.push_back(e);
}
}
was = temp;
temp.clear();
assert(is_sorted(all(was)));
m = (int)was.size();
for (int i = 0; i < m; ++i) {
// cout << was[i].l << " " << was[i].r << " " << was[i].y << endl;
was[i].i = i;
}
assigner.upd(0, n - 1, -1);
for (int i = 0; i < m; ++i) {
auto e = was[i];
vert_edge(x[e.l], e.i, assigner.query(e.l));
vert_edge(x[e.r], e.i, assigner.query(e.r));
assigner.upd(e.l, e.r, e.i);
}
assigner.upd(0, n - 1, -1);
for (int i = m; i--; ) {
auto e = was[i];
int j = assigner.query(e.l);
if (j != -1 && h[e.l] >= was[j].y) {
vert_edge(x[e.l], e.i, j);
}
j = assigner.query(e.r);
if (j != -1 && h[e.r] >= was[j].y) {
vert_edge(x[e.r], e.i, j);
}
assigner.upd(e.l, e.r, e.i);
}
for (int i = 0; i < m; ++i) {
if (was[i].y == 0) {
continue;
}
sort(all(ord[i]), [&](int a, int b) {
return pt[a].x < pt[b].x;
});
for (int j = 0; j + 1 < (int)ord[i].size(); ++j) {
add_edge(ord[i][j], ord[i][j + 1]);
}
}
int from = get_id(x[st], 0), to = get_id(x[fi], 0);
fill_n(dist, N, LLINF);
dist[from] = 0;
using T = pair<ll, int>;
priority_queue<T, vector<T>, greater<T>> q;
q.emplace(dist[from], from);
// cout << "from " << pt[from].x << " " << pt[from].y << endl;
// cout << "to " << pt[to].x << " " << pt[to].y << endl;
while (q.size()) {
ll d;
int v;
tie(d, v) = q.top(); q.pop();
if (dist[v] != d) {
continue;
}
for (auto e : g[v]) {
int u = e.x, w = e.y;
if (dist[u] > dist[v] + w) {
dist[u] = dist[v] + w;
q.emplace(dist[u], u);
}
}
}
if (dist[to] > LLINF / 2) {
return -1;
} else {
return dist[to];
}
}
#ifdef LC
#include "grader.cpp"
#endif
