#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) {
{ // modification
auto modify = [&](int u){
int m = l.size();
set <int> st;
for ( int i = 0; i < m; i++ ){
if ( y[i] <= h[u] && l[i] <= u && r[i] >= u ){
l.pb(l[i]), r.pb(u); y.pb(y[i]);
l.pb(u), r.pb(r[i]); y.pb(y[i]);
st.insert(i);
}
}
vector <int> l_, r_, y_;
for ( int i = 0; i < (int)l.size(); i++ ){
if ( !st.count(i) ){
l_.pb(l[i]), r_.pb(r[i]), y_.pb(y[i]);
}
}
l = l_, r = r_, y = y_;
};
modify(s), modify(g);
}
int n = x.size(), m = l.size();
vector <vector<ar<int,3>>> H(n);
vector <vector<int>> qry(n);
for ( int i = 0; i < m; i++ ){
H[l[i]].pb({1, y[i], i});
H[r[i]].pb({0, y[i], i});
qry[r[i]].pb(i);
}
y.pb(0), l.pb(s), r.pb(s); // start
y.pb(0), l.pb(g), r.pb(g); // end
qry[s].pb(m), qry[g].pb(m + 1);
vector <int> D(m + 2, -1), U(m + 2, -1);
// m -> (0), m + 1 -> (n - 1)
set <pair<int,int>> st;
for ( int i = 0; i < n; i++ ){
for ( auto &[t, u, j]: H[i] ){
if ( t > 0 ){
st.insert({u, j});
} else if ( i + 1 < n ){ // for (n - 1, 0)
st.erase({u, j});
}
}
for ( auto &j: qry[i] ){
auto it = st.lower_bound({y[j], -1});
if ( it != st.end() ){
U[j] = it -> second;
}
if ( it != st.begin() ){
D[j] = prev(it) -> second;
}
}
}
//~ cout << "Up & Down : \n";
//~ for ( int i = 0; i < m + 2; i++ ){
//~ cout << U[i] << " " << D[i] << ln;
//~ } cout << ln;
vector <vector<int>> rng(m + 2);
for ( int i = 0; i < m + 2; i++ ){
rng[i].pb(l[i]);
rng[i].pb(r[i]);
if ( U[i] == i ) U[i] = -1;
if ( D[i] == i ) D[i] = -1;
if ( U[i] != -1 ){
rng[U[i]].pb(r[i]);
}
if ( D[i] != -1 ){
rng[D[i]].pb(r[i]);
}
}
map <ar<int,2>,int> id;
vector <vector<ar<i64,2>>> adj;
int k = 0;
auto get = [&](int u, int v){
if ( !id.count({u, v}) ){
id[{u, v}] = k++;
adj.pb(vector <ar<i64,2>>());
}
return id[{u, v}];
};
for ( int i = 0; i < m + 2; i++ ){
auto &p = rng[i];
sort(all(p));
p.resize(unique(all(p)) - p.begin());
{ // assigning index
for ( auto x: p ) get(x, y[i]);
}
for ( int j = 0; j + 1 < (int)p.size(); j++ ){
int u = get(p[j], y[i]), v = get(p[j + 1], y[i]);
adj[u].pb({v, x[p[j + 1]] - x[p[j]]}); // to the right
adj[v].pb({u, x[p[j + 1]] - x[p[j]]});
//~ cout << "{" << p[j] << " " << y[i] << "} {" << p[j + 1] << " " << y[i] << "} " << x[p[j + 1]] - x[p[j]] << ln;
}
if ( D[i] != -1 ){ // down
int u = get(r[i], y[i]), v = get(r[i], y[D[i]]);
//~ cout << "{" << r[i] << " " << y[i] << "} {" << r[i] << " " << y[D[i]] << "} " << y[i] - y[D[i]] << ln;
adj[u].pb({v, y[i] - y[D[i]]});
adj[v].pb({u, y[i] - y[D[i]]});
}
if ( U[i] != -1 ){ // up
int u = get(r[i], y[i]), v = get(r[i], y[U[i]]);
//~ cout << "{" << r[i] << " " << y[i] << "} {" << r[i] << " " << y[U[i]] << "} " << -y[i] + y[U[i]] << ln;
adj[u].pb({v, -y[i] + y[U[i]]});
adj[v].pb({u, -y[i] + y[U[i]]});
}
}
vector <i64> dp(k, inf);
priority_queue <ar<i64,2>> q;
int u = get(s, 0);
dp[u] = 0;
q.push({0, u});
while ( !q.empty() ){
auto [val, u] = q.top();
q.pop();
if ( -val != dp[u] ) continue;
for ( auto &[v, w]: adj[u] ){
if ( chmin(dp[v], dp[u] + w) ){
q.push({-dp[v], v});
}
}
}
u = get(g, 0);
if ( dp[u] == inf ){
dp[u] = -1;
}
return dp[u];
}
