#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();
if ( s == 0 && g == n - 1 ){ // subtask #3
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(0), r.pb(0); // start
y.pb(0), l.pb(n - 1), r.pb(n - 1); // end
qry[0].pb(m), qry[n - 1].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(0, 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(n - 1, 0);
if ( dp[u] == inf ){
dp[u] = -1;
}
return dp[u];
} else{
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();
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;
}
}
