#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int f) {
int n = x.size();
int m = l.size();
vector<int> ord1(n);
iota(ord1.begin(), ord1.end(), 0);
sort(ord1.begin(), ord1.end(), [&](int a, int b) -> bool {
return h[a] > h[b];
});
vector<int> ord2(m);
iota(ord2.begin(), ord2.end(), 0);
sort(ord2.begin(), ord2.end(), [&](int a, int b) -> bool {
return y[a] > y[b];
});
vector<ll> minp(n, 1e18), minpi(n, -1);
set<pair<ll, int>> st;
vector<vector<pair<int, ll>>> g;
int ptr1 = 0;
for (int idx : ord2) {
while (ptr1 < n && y[idx] <= h[ord1[ptr1]]) {
st.emplace(x[ord1[ptr1]], ord1[ptr1]);
ptr1++;
}
auto bg = st.find({x[l[idx]], l[idx]});
auto en = st.find({x[r[idx]], r[idx]});
en++;
auto ptr = bg, prv = bg;
while (ptr != en) {
g.emplace_back();
int th = g.size() - 1;
int i = ptr->second;
if (minpi[i] != -1) {
g[th].emplace_back(minpi[i], minp[i] - y[idx]);
g[minpi[i]].emplace_back(th, minp[i] - y[idx]);
}
minpi[i] = th;
minp[i] = y[idx];
if (ptr != bg) {
int pr = g.size() - 2;
g[pr].emplace_back(th, ptr->first - prv->first);
g[th].emplace_back(pr, ptr->first - prv->first);
}
prv = ptr;
ptr++;
}
}
if (minpi[s] == -1 || minpi[f] == -1) return -1;
int sz = g.size();
vector<ll> dst(sz, INT64_MAX / 2);
dst[minpi[s]] = 0;
st.clear();
for (int i = 0; i < sz; i++) {
st.emplace(dst[i], i);
}
while (!st.empty()) {
auto [d, s] = *st.begin();
st.erase(st.begin());
for (auto [i, w] : g[s]) {
if (dst[i] > dst[s] + w) {
st.erase({dst[i], i});
dst[i] = dst[s] + w;
st.emplace(dst[i], i);
}
}
}
if (dst[minpi[f]] >= INT64_MAX / 2) return -1;
ll ans = dst[minpi[f]];
ans += minp[s] + minp[f];
return ans;
}
