#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const int MAXND = 1000005;
int hv[MAXN], ind = -1;
vector<int> add;
map<int, int> mp[MAXN];
vector<pair<int, ll>> adj[MAXND];
ll dist[MAXND];
struct node{
int s, e, m; vector<pair<int, int>> vec;
node *l, *r;
node (int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
if (s == e) vec.push_back({hv[s], s});
else{
l = new node(s, m); r = new node(m + 1, e);
auto &lv = l->vec, &rv = r->vec;
int lind = 0, lsz = lv.size(), rind = 0, rsz = rv.size();
while (lind < lsz && rind < rsz){
if (lv[lind].first >= rv[rind].first){
vec.push_back(lv[lind]);
lind++;
}
else{
vec.push_back(rv[rind]);
rind++;
}
}
while (lind < lsz){
vec.push_back(lv[lind]);
lind++;
}
while (rind < rsz){
vec.push_back(rv[rind]);
rind++;
}
}
}
void query(int x, int y, int h){
if (x == s && y == e){
int sz = e - s + 1;
for (int i = 0; i < sz && vec[i].first >= h; i++) add.push_back(vec[i].second);
return;
}
else if (y <= m) l->query(x, y, h);
else if (x > m) r->query(x, y, h);
else{
l->query(x, m, h); r->query(m + 1, y, h);
}
}
};
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
int n = x.size(), m = y.size();
for (int i = 0; i < n; i++) hv[i] = h[i];
node *root = new node(0, n - 1);
mp[s][0] = ++ind; mp[g][0] = ++ind;
for (int i = 0; i < m; i++){
add.clear();
root->query(l[i], r[i], y[i]);
sort(add.begin(), add.end());
int prev = -1, px;
for (int b : add){
int aind;
if (mp[b].count(y[i])) aind = mp[b][y[i]];
else mp[b][y[i]] = aind = ++ind;
if (prev != -1){
adj[aind].push_back({prev, x[b] - px});
adj[prev].push_back({aind, x[b] - px});
}
prev = aind; px = x[b];
}
}
for (int i = 0; i < n; i++){
int prev = -1, ph;
for (auto &[height, aind] : mp[i]){
if (prev != -1){
adj[aind].push_back({prev, height - ph});
adj[prev].push_back({aind, height - ph});
}
prev = aind; ph = height;
}
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, 0});
for (int i = 0; i <= ind; i++) dist[i] = 1e18;
dist[0] = 0;
while (!pq.empty()){
ll d; int i; tie(d, i) = pq.top(); pq.pop();
if (dist[i] != d) continue;
if (i == 1) return d;
for (auto &[nn, nd] : adj[i]){
if (d + nd < dist[nn]){
dist[nn] = d + nd;
pq.push({dist[nn], nn});
}
}
}
return -1;
}
