#include <bits/stdc++.h>
#include "walk.h"
// #include "grader.cpp"
using namespace std;
using ll = long long;
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define pii pair<int, int>
ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int G) {
int n = sz(X), m = sz(L);
vector<int> ordq(m);
iota(all(ordq), 0);
sort(all(ordq), [&](int x, int y) {
return Y[x] < Y[y] || (Y[x] == Y[y] && x < y);
});
reverse(all(ordq));
vector<int> ord(n);
iota(all(ord), 0);
sort(all(ord), [&](int x, int y) {
return H[x] < H[y] || (H[x] == H[y] && x < y);
});
set<int> s;
int ind = n - 1;
vector<pii> E[n];
for (auto i : ordq) {
while (~ind && Y[i] <= H[ord[ind]]) s.insert(ord[ind--]);
int x = L[i];
while (x != R[i]) {
// int y = -1;
// for (int j = x + 1; j <= R[i] && !~y; j++)
// if (Y[i] <= H[j]) y = j;
// if (!~y) break;
auto y = s.upper_bound(x);
if (y == s.end()) break;
E[x].push_back({x, Y[i]});
E[x].push_back({*y, Y[i]});
E[*y].push_back({*y, Y[i]}); //don't need?
E[*y].push_back({x, Y[i]});
x = *y;
}
}
priority_queue<pair<ll, pii>> q;
vector<map<int, ll>> dis(n);
q.push({0, {S, 0}}); dis[S][0] = 0;
while (!q.empty()) {
auto [d, x] = q.top(); d = -d; q.pop();
if (d != dis[x.ff][x.ss]) continue;
for (auto [i, y] : E[x.ff]) {
if (dis[i].find(y) == dis[i].end() || d + abs(x.ss - y) + abs(X[x.ff] - X[i]) < dis[i][y]) {
dis[i][y] = d + abs(x.ss - y) + abs(X[x.ff] - X[i]);
q.push({-dis[i][y], {i, y}});
}
}
}
if (dis[G].empty()) return -1;
ll mn = LLONG_MAX;
for (auto i : dis[G])
mn = min(mn, i.ff + i.ss);
return mn;
}
