#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const ll INF =1e18;
#ifdef LOCAL
#include "../../../../../MixedFunc/pretty_debug.h"
#else
#define debug(...) //ignore
#endif
template<class T>
auto dijkstra(int source, vector<vector<pair<int, T>>> &g) {
int n = sz(g);
vector<T> dist(n, numeric_limits<T>::max());
vector<pair<int,T> > dad(n, {-1, 0});
priority_queue<pair<T,int> > pq;
dist[source] = 0;
pq.emplace(0,source);
while(!pq.empty()) {
T d; int x;
tie(d,x) = pq.top();
d = -d;
pq.pop();
if(d > dist[x]) continue;
for(auto [y,w] : g[x]) {
if(dist[y] > d + w) {
dist[y] = d + w;
dad[y] = {x, w};
pq.emplace(-dist[y], y);
}
}
}
return pair{dist, dad};
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
int n = sz(x), m = sz(l);
debug(n,m);
auto st12 = [&](){
map<ll, map<ll, int> > V;
map<int, pair<ll,ll>> iV;
vector<vector<pair<int,ll>>> E;
auto at = [&](int i, int h) {
if (!V[x[i]].count(h)) {
V[x[i]][h] = sz(E);
iV[sz(E)] = {x[i],h};
E.emplace_back();
}
return V[x[i]][h];
};
auto edge = [&](int a, int b, ll c) {
E[a].emplace_back(b,c);
E[b].emplace_back(a,c);
};
auto edges = [&](map<ll,int> vert) {
pair<ll,int> a = *vert.begin();
vert.erase(vert.begin());
for(auto b : vert) {
edge(a.second, b.second, b.first-a.first);
a = b;
}
};
at(s,0);
at(g,0);
rep(i,0,m) {
l[i], r[i], y[i];
map<ll, int> vert;
vert[x[l[i]]] = at(l[i], y[i]);
vert[x[r[i]]] = at(r[i], y[i]);
// temporary
rep(j,l[i]+1, r[i]) if(h[j] >= y[i])
vert[x[j]] = at(j, y[i]);
edges(vert);
}
for(auto v: V) edges(v.second);
debug(sz(E))
auto[dist, dad] = dijkstra(at(s,0),E);
for(int q = at(g,0); dad[q].first != -1; q = dad[q].first) {
debug(iV[q]);
}
ll ans = dist[at(g, 0)];
if (ans >= INF) ans = -1;
return ans;
};
auto st34 = [&](){
vector<vi> start(n), end(n);
rep(i,0,m) {
start[l[i]].eb(y[i]);
end[r[i]].eb(y[i]);
}
start[n-1].eb(0);
end[0].eb(0);
// cost[h] = get to dp[h]
map<int, ll> cost;
map<int, ll> cnt;
cost[0] = 0;
cnt[0] = 1;
debug(n);
rep(i,0,n) {
debug(i, cost);
for(int H : start[i]) {
if(cnt[H]++ == 0) {
debug("add", H);
ll c = INF;
auto C = [&](auto p) { return p.second + abs(p.first - H); };
auto it = cost.lower_bound(H);
if(it != cost.end()) c = min(c, C(*it));
if(it != cost.begin()) c = min(c, C(*--it));
cost[H] = c;
}
}
for(int H : end[i]) {
if(--cnt[H] == 0) {
debug("rem", H);
cost.erase(H);
}
}
}
debug(cost)
debug(x[n-1] - x[0]);
ll ans = cost[0] + x[n-1]-x[0];
if (ans >= INF) ans = -1;
return ans;
};
if (s == 0 && g == n-1) return st34();
else return st12();
}
