#include "walk.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
const int N = 1e5 + 10;
int n, m;
vector<int> x, h, l, r, y;
int Get_Max(int l, int r){ // [l, r]
// cerr << ""
if(r < l) return -1;
return h[l];
int mx = h[l];
for(int i = l; i <= r; i++)
mx = max(mx, h[i]);
return mx;
}
vector<pii> G[N];
void Add_Edge(int a, int b){
// cerr << "!! " << a << ' ' << b << '\n';
int ls = max(l[a], l[b]);
int rs = min(r[a], r[b]);
if(max(y[a], y[b]) <= Get_Max(ls, rs)){
G[a].pb({b, abs(y[a] - y[b])});
G[b].pb({a, abs(y[a] - y[b])});
}
// cerr << "!! " << a << ' ' << b << '\n';
}
vector<int> ins[N], dl[N];
void Add(vector<int> sg){
for(int i = 0; i < N; i++) ins[i].clear(), dl[i].clear();
for(int i : sg){
ins[l[i]].pb(i);
dl[r[i]].pb(i);
}
set< pair<int, int> > st; // y id
for(int i = 0; i < N; i++){
// cerr << "^^ " << i << '\n';
for(auto u : ins[i]){
// cerr << "&& " << u << ' ' << y[u] << '\n';
st.insert({y[u], u});
auto it = st.find({y[u], u});
if(it != st.begin())
Add_Edge(it->S, prev(it) -> S);
if(next(it) != st.end())
Add_Edge(it->S, next(it) -> S);
}
// cerr << "^^ " << i << '\n';
for(auto u : dl[i]){
auto it = st.find({y[u], u});
if(it != st.begin() && next(it) != st.end())
Add_Edge(next(it) -> S, prev(it) -> S);
st.erase(it);
}
}
}
ll dis[N];
typedef pair<ll, ll> pll;
ll Djik(int src, int des){
memset(dis, 31, sizeof dis);
dis[src] = 0;
set<pll> st;
st.insert({dis[src], src});
while(!st.empty()){
int fr = st.begin() -> S;
st.erase(st.begin());
for(auto [adj, w] : G[fr]){
if(dis[adj] > dis[fr] + w){
st.erase({dis[adj], adj});
dis[adj] = dis[fr] + w;
st.insert({dis[adj], adj});
}
}
}
return dis[des];
}
ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int s, int g) {
if(s > g) swap(s, g);
x = _x;
h = _h;
ll ans = x[g] - x[s];
_l.pb(s); _r.pb(s); _y.pb(0);
_l.pb(g); _r.pb(g); _y.pb(0);
int src = _l.size() - 2;
int des = _r.size() - 1;
n = _x.size();
m = _l.size();
l = _l;
r = _r;
y = _y;
vector<int> lft, mid, rgt;
for(int i = 0; i < m; i++) mid.pb(i);
// debug("A");
Add(lft);
// debug("B");
Add(mid);
// debug("C");
Add(rgt);
// debug("D");
ans += Djik(src, des);
int max_len = 1000000000;
return ans > 1ll * (n + m) * max_len ? -1 : ans;
}
