#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];
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();
for(int i = 0; i < m; i++) {
for(int building = l[i]; building <= r[i]; building++) {
if(y[i] <= h[building]) in[building].push_back(y[i]);
}
}
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++) {
vector<int> ver;
// cout << "seg: " << l[i] << ' ' << r[i] << ' ' << y[i] << '\n';
for(int st = l[i]; st <= r[i]; st++) {
if(h[st] >= y[i]) {
ver.push_back(st);
// cout << '[' << st << ' ' << find(in[st].begin(), in[st].end(), y[i]) - in[st].begin() << ']' << ' ';
}
}
// cout << '\n';
for(int z = 0; z < (int)ver.size() - 1; z++) {
int st = ver[z], next = ver[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]});
}
// cout << '\n';
}
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];
}
