#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
#define pq priority_queue
const int N = 2e6 + 5, INF = 1e18;
map<pii, int> nd;
map<int, vec<int>> pnt;
map<int, vec<pii>> adj; // {node, distance}
int st, fn;
arr<bool, N> vs;
arr<int, N> dst;
pq<pii, vec<pii>, greater<pii>> ord;
void djk() {
dst.fill(INF);
dst[st] = 0, ord.push({0, st});
while (ord.size()) {
int u = ord.top().sec; ord.pop();
if (vs[u]) continue;
vs[u] = true;
for (pii x : adj[u]) {
int nw_dst = dst[u] + x.sec;
if (nw_dst >= dst[x.fir]) continue;
dst[x.fir] = nw_dst, ord.push({nw_dst, x.fir});
}
}
}
int min_distance(vec<sig> _x, vec<sig> _h, vec<sig> _l, vec<sig> _r, vec<sig> _y, sig _s, sig _f) {
vec<vec<int>> twr, wlk;
for (int i = 0; i < _x.size(); i++) {
vec<int> x = {_h[i], _x[i]};
twr.push_back(x);
}
for (int i = 0; i < _l.size(); i++) {
vec<int> x = {_y[i], _x[_l[i]], _x[_r[i]]};
wlk.push_back(x);
}
sort(twr.begin(), twr.end()), sort(wlk.begin(), wlk.end());
for (int i = 0; i < _x.size(); i++) {
int id = nd.size() + 1;
nd[{_x[i], 0}] = id;
pnt[_x[i]].push_back(0);
}
set<int> ps;
while (wlk.size()) {
vec<int> x = wlk.back(); wlk.pop_back();
while (twr.size() && twr.back()[0] >= x[0]) {
vec<int> y = twr.back(); twr.pop_back();
ps.insert(y[1]);
}
if (!nd.count({x[1], x[0]})) {
int id = nd.size() + 1;
nd[{x[1], x[0]}] = id;
pnt[x[1]].push_back(x[0]);
}
if (!nd.count({x[2], x[0]})) {
int id = nd.size() + 1;
nd[{x[2], x[0]}] = id;
pnt[x[2]].push_back(x[0]);
}
int u = nd[{x[1], x[0]}], v = nd[{x[2], x[0]}], d = x[2] - x[1];
adj[u].push_back({v, d}), adj[v].push_back({u, d});
// for (auto it = ps.find(x[1]); it != ps.end(); it++) {
// if (!nd.count({*it, x[0]})) {
// int id = nd.size() + 1;
// nd[{*it, x[0]}] = id;
// pnt[*it].push_back(x[0]);
// }
// if (*it != x[1]) {
// int u = nd[{*it, x[0]}], v = nd[{*next(it, -1), x[0]}], d = *it - *next(it, -1);
// adj[u].push_back({v, d}), adj[v].push_back({u, d});
// }
// if (*it == x[2]) break;
// }
}
for (pair<int, vec<int>> x : pnt) {
sort(x.sec.begin(), x.sec.end());
for (int i = 0; i < x.sec.size() - 1; i++) {
int u = nd[{x.fir, x.sec[i]}], v = nd[{x.fir, x.sec[i + 1]}], d = x.sec[i + 1] - x.sec[i];
adj[u].push_back({v, d}), adj[v].push_back({u, d});
}
}
// for (pair<pii, int> x : nd) {
// cout << x.fir.fir << " " << x.fir.sec << endl;
// }
st = nd[{_x[_s], 0}], fn = nd[{_x[_f], 0}];
djk();
if (!vs[fn]) return -1;
return dst[fn];
}
