#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define ln '\n'
using i64 = long long;
template <class F, class S>
bool chmin(F &u, const S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
const i64 inf = 1e15;
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
int n = x.size(), m = l.size();
vector <vector<ar<int,3>>> H(n + 1);
{ // shifting y
y.pb(0);
for ( int i = m; i > 0; i-- ){
y[i] = y[i - 1];
} y[0] = 0;
}
for ( int i = 1; i <= m; i++ ){
H[l[i - 1]].pb({1, y[i], i});
H[r[i - 1] + 1].pb({0, y[i], i});
}
set <pair<int,int>> st;
vector <vector<int>> a(n, {0}), mp(m + 1);
auto V = a;
for ( int i = 0; i < n; i++ ){
for ( auto &[t, y, j]: H[i] ){
if ( t > 0 ){
st.insert({y, j});
} else st.erase({y, j});
}
auto it = st.begin();
while ( it != st.end() && it -> first <= h[i] ){
a[i].pb(it -> second);
V[i].pb(it -> first);
mp[it -> second].pb(i);
it = next(it);
}
}
vector <vector<i64>> dp(n);
vector <vector<int>> id(n);
for ( int i = 0; i < n; i++ ){
sort(all(a[i]), [&](int &u, int &v){
return y[u] < y[v];
});
int s = a[i].size();
dp[i].resize(s, inf);
id[i].resize(s);
for ( int j = 1; j < s; j++ ){
int x = a[i][j];
id[i][j] = lower_bound(all(mp[x]), i) - mp[x].begin();
}
}
dp[s][0] = 0;
priority_queue <ar<i64,3>> q;
q.push({0, s, 0});
while ( !q.empty() ){
auto [val, u, j] = q.top();
q.pop();
if ( -val != dp[u][j] ) continue;
if ( j != 0 ){ // using skywalk a[u][j]
int t = a[u][j];
for ( auto i: {id[u][j] - 1, id[u][j] + 1} ){
if ( i < 0 || i >= (int)mp[t].size() ){
continue;
}
int v = mp[t][i], nxt = lower_bound(all(V[v]), y[t]) - V[v].begin();
assert(a[v][nxt] == t);
if ( chmin(dp[v][nxt], dp[u][j] + abs(x[v] - x[u])) ){
q.push({-dp[v][nxt], v, nxt});
}
}
}
for ( auto i: {j + 1, j - 1} ){
if ( i < 0 || i >= (int)dp[u].size() ){
continue;
}
if ( chmin(dp[u][i], dp[u][j] + abs(y[a[u][j]] - y[a[u][i]])) ){
q.push({-dp[u][i], u, i});
}
}
}
i64 ans = dp[g][0];
if ( ans == inf ){
ans = -1;
}
return ans;
}
