#include "walk.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100001
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> ptr;
typedef array <int, 3> a3;
vector <vector <int> > g;
vector <a3> edge;
vector <int> nums[N], who[N];
vector <ll> dst, dstr;
gp_hash_table <int, int> idr[N];
void add(int a, int b, int cost)
{
g[a].pb(sz(edge));
g[b].pb(sz(edge));
edge.pb({a, b, cost});
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int to)
{
int n = sz(x);
int m = sz(l);
set <pair <int, int> > st; st.clear();
vector <pair <int, int> > pr; pr.clear();
for (int j = 0; j < m; j++) {pr.pb({l[j], j + 1}); pr.pb({r[j] + 1, -(j + 1)});}
sort(pr.begin(), pr.end());
int u = 0;
for (int i = 0; i < n; i++)
{
while (u < sz(pr) && pr[u].F <= i)
{
if (pr[u].S > 0) st.insert({y[pr[u].S - 1], pr[u].S - 1});
else st.erase({y[-pr[u].S - 1], -pr[u].S - 1});
u++;
}
auto it = st.upper_bound(ptr(h[i], 1e9));
if (it != st.begin())
{
it--;
while (1)
{
nums[i].pb((*it).S);
if (it == st.begin()) break;
it--;
}
}
}
int id = 0;
ll ans = 1e18;
set <pair <pair <ll, int>, int> > str;
for (int i = 0; i < n; i++)
for (auto j : nums[i])
{
idr[i][j] = id++;
g.emplace_back();
dst.pb(-1);
dstr.pb(-1);
for (auto jr : nums[i])
{
if (jr == j) break;
add(id - 1, idr[i][jr], abs(y[jr] - y[j]));
}
if (to == i) {dst[id - 1] = 0; str.insert({{y[j], id - 1}, 0});}
if (s == i) {dstr[id - 1] = 0; str.insert({{y[j], id - 1}, 1});}
}
for (int i = 0; i < n; i++)
for (auto j : nums[i])
{
for (auto I : who[j])
add(idr[i][j], idr[I][j], abs(x[i] - x[I]));
who[j].pb(i);
}
while (sz(str))
{
pair <pair <ll, int>, int> pt = *str.begin(); str.erase(str.begin());
if (pt.F.F >= ans) return ans;
for (auto ip : g[pt.F.S])
{
a3 itr = edge[ip];
ll s = pt.F.F + itr[2];
if (itr[0] == pt.F.S) swap(itr[0], itr[1]);
if (ans <= s) continue;
if (pt.S == 0)
{
if (dst[itr[0]] != -1 && dst[itr[0]] <= s) continue;
if (dstr[itr[0]] != -1) {ans = min(ans, dstr[itr[0]] + s); continue;}
if (dst[itr[0]] != -1) str.erase({{dst[itr[0]], itr[0]}, 0});
dst[itr[0]] = s;
str.insert({{s, itr[0]}, 0});
}
else
{
if (dstr[itr[0]] != - 1 && dstr[itr[0]] <= s) continue;
if (dst[itr[0]] != -1) {ans = min(ans, dst[itr[0]] + s); continue;}
if (dstr[itr[0]] != -1) str.erase({{dstr[itr[0]], itr[0]}, 1});
dstr[itr[0]] = s;
str.insert({{s, itr[0]}, 1});
}
}
}
if (ans == 1e18) return -1;
return ans;
}
