#include<bits/stdc++.h>
#include "walk.h"
using namespace std;
using ll = long long;
int n, m;
const int N = 1e5 + 10;
const int M = 2e6 + 10;
const ll INF = 1e15;
vector<pair<int, ll>> G[M];
vector<int> in[N];
int inx[N];
vector<int> cities[N];
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
n = (int)x.size(), m = (int)y.size();
// first = height, second = type, third = index
vector<pair<int, pair<int, int>>> ord;
for(int i = 0; i < n; i++)
ord.push_back({h[i], {1, i}});
for(int i = 0; i < m; i++)
ord.push_back({y[i], {0, i}});
sort(ord.rbegin(), ord.rend());
set<int> lux;
for(auto cur : ord) {
auto [type, inx] = cur.second;
if(type)
lux.insert(inx);
else {
int x = l[inx] - 1;
while(*(--lux.end()) > x) {
x = *lux.upper_bound(x);
if(x > r[inx]) break;
in[x].push_back(y[inx]);
cities[inx].push_back(x);
}
}
}
for(int i = 0; i < n; i++) {
in[i].push_back(0);
sort(in[i].begin(), in[i].end());
if(i) inx[i] = inx[i - 1] + (int)in[i - 1].size();
for(int r = 0; r < (int)in[i].size() - 1; r++) {
G[inx[i] + r].push_back({inx[i] + r + 1, in[i][r + 1] - in[i][r]});
G[inx[i] + r + 1].push_back({inx[i] + r, in[i][r + 1] - in[i][r]});
}
}
// for(int i = 0; i < n; i++) {
// cout << "cur: " << i << '\n';
// cout << '[';
// for(int t : in[i])
// cout << t << " ";
// cout << ']';
// cout << '\n';
// }
for(int i = 0; i < m; i++) {
for(int z = 0; z < (int)cities[i].size() - 1; z++) {
int st = cities[i][z], next = cities[i][z + 1];
int pos1 = find(in[st].begin(), in[st].end(), y[i]) - in[st].begin();
int pos2 = find(in[next].begin(), in[next].end(), y[i]) - in[next].begin();
G[inx[st] + pos1].push_back({inx[next] + pos2, x[next] - x[st]});
G[inx[next] + pos2].push_back({inx[st] + pos1, x[next] - x[st]});
}
}
int T = inx[n - 1] + (int)in[n - 1].size();
vector<ll> dist(T, INF);
dist[inx[g]] = 0;
set<pair<ll, int>> st;
for(int i = 0; i < T; i++) {
st.insert({dist[i], i});
}
while(!st.empty()) {
int s = st.begin()->second;
st.erase(st.begin());
for(auto [to, w] : G[s]) {
if(dist[to] > dist[s] + w) {
st.erase({dist[to], to});
dist[to] = dist[s] + w;
st.insert({dist[to], to});
}
}
}
int fin = inx[s];
if(dist[fin] == INF) return -1;
return dist[fin];
}
