#include <bits/stdc++.h>
#define ll long long
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#include "walk.h"
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const ll INF = 1e18;
struct seg {
int N; vector<ll> tree;
seg(int n) : N(1<<(__lg(n)+1)), tree(2*N, INF) {}
void update(int pos, ll x) {
tree[pos+N] = x;
for (int i = (pos + N) >> 1; i; i >>= 1) tree[i] = min(tree[i*2], tree[i*2+1]);
}
ll query(int node, int nl, int nr, int ql, int qr) {
if (ql > nr || qr < nl) return INF;
if (ql <= nl && nr <= qr) return tree[node];
int mid = (nl+nr)/2;
return min(query(node*2, nl, mid, ql, qr), query(node*2+1, mid+1, nr, ql, qr));
}
ll query(int l, int r) {
return query(1, 0, N-1, l, r);
}
};
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
int n = sz(x), m = sz(l);
if (s == 0 && g == n-1) {
vector<ar<int, 3>> lines;
for (int i = 0; i < m; i++) lines.push_back({l[i], r[i], y[i]});
sort(all(lines));
vector<ll> dp(m, INF);
sort(all(y));
y.erase(unique(all(y)), y.end());
const int N = sz(y);
auto compress = [&](int x) {
return lower_bound(all(y), x) - y.begin();
};
seg st1(N), st2(N);
for (auto &[l, r, y] : lines) y = compress(y);
for (int i = 0; i < m; i++) if (lines[i][0] == 0) dp[i] = y[lines[i][2]];
vector<vector<int>> rem(n);
int t = 0;
for (int i = 0; i < m; i++) {
ckmin(dp[i], y[lines[i][2]] + st1.query(0, lines[i][2]));
ckmin(dp[i], -y[lines[i][2]] + st2.query(lines[i][2], N-1));
st1.update(lines[i][2], dp[i] - y[lines[i][2]]);
st2.update(lines[i][2], dp[i] + y[lines[i][2]]);
while (t <= min(n-1, lines[i][0])) {
for (int x : rem[t]) {
st1.update(lines[x][2], INF);
st2.update(lines[x][2], INF);
}
t++;
}
rem[lines[i][1]].emplace_back(i);
}
ll ans = INF;
for (int i = 0; i < m; i++) if (lines[i][1] == n-1) ckmin(ans, dp[i] + y[lines[i][2]]);
return ans == INF ? -1 : ans + x[n-1];
}
vector<int> idx(n);
iota(all(idx), 0);
sort(all(idx), [&](int x, int y) { return h[x] > h[y]; });
vector<int> idx2(m);
iota(all(idx2), 0);
sort(all(idx2), [&](int X, int Y) { return y[X] > y[Y]; });
set<int> who;
vector<ar<int, 3>> edges;
for (int i = 0, on = 0; i < m; i++) {
int L = l[idx2[i]], R = r[idx2[i]], H = y[idx2[i]];
while (on < n && h[idx[on]] >= H) {
who.insert(idx[on++]);
}
int lst = -1;
auto it1 = who.lower_bound(L);
if (it1 == who.end() || *it1 > R) continue;
lst = *it1;
while (1) {
auto it = who.upper_bound(lst);
if (it == who.end() || *it > R) break;
edges.push_back({lst, *it, H});
lst = *it;
}
}
vector<vector<int>> nodes(n);
vector<map<int, vector<int>>> adj(n);
for (auto [l, r, H] : edges) {
nodes[l].emplace_back(H);
nodes[r].emplace_back(H);
adj[l][H].push_back(r);
adj[r][H].push_back(l);
}
nodes[s].emplace_back(0);
nodes[g].emplace_back(0);
for (int i = 0; i < n; i++) {
sort(all(nodes[i]));
nodes[i].erase(unique(all(nodes[i])), nodes[i].end());
}
vector<map<int, ll>> dist(n);
dist[s][0] = 0;
priority_queue<ar<ll, 3>, vector<ar<ll, 3>>, greater<ar<ll, 3>>> q;
q.push({0, s, 0});
auto rlx = [&](int v1, int x1, int v2, int x2) {
ll new_dist = dist[v1][x1] + abs(x[v1] - x[v2]) + abs(x1 - x2);
if (!dist[v2].count(x2) || dist[v2][x2] > new_dist) {
dist[v2][x2] = new_dist;
q.push({dist[v2][x2], v2, x2});
}
};
while (q.size()) {
auto [cost, v, i] = q.top(); q.pop();
if (cost != dist[v][i]) continue;
auto it = upper_bound(all(nodes[v]), i);
if (it != nodes[v].end() && *it <= h[v]) {
rlx(v, i, v, *it);
}
assert(it != nodes[v].begin());
it--;
if (it != nodes[v].begin() && i <= h[v]) {
rlx(v, i, v, *prev(it));
}
for (int x : adj[v][i]) {
rlx(v, i, x, i);
}
}
return dist[g].count(0) ? dist[g][0] : -1;
}
