#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 <pair <int, int> > > g;
vector <int> nums[N], who[N], db[N], del[N];
char mk[N * 10];
ll dst[N * 10];
unordered_map <int, int> idr[N];
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);
if (s > to) swap (s, to);
set <pair <int, int> > st; st.clear();
for (int j = 0; j < m; j++)
{db[l[j]].pb(j); del[r[j]].pb(j);}
for (int i = 0; i < n; i++)
{
for (auto j : db[i])
st.insert({y[j], j});
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--;
}
}
for (auto j : del[i])
st.erase({y[j], j});
}
int id = 0;
ll ans = 1e18;
set <pair <ll, int> > str;
set <pair <int, int> > se; se.clear();
for (int i = 0; i < n; i++)
for (auto j : nums[i])
{
if (i == s) se.insert({id, y[j]});
idr[i][j] = id++;
g.emplace_back();
dst[id - 1] = -1;
mk[id - 1] = 'a';
for (auto jr : nums[i])
{
if (jr == j) break;
g[id - 1].pb({idr[i][jr], abs(y[jr] - y[j])});
g[idr[i][jr]].pb({id - 1, abs(y[jr] - y[j])});
}
if (to == i) {dst[id - 1] = 0; str.insert({y[j], id - 1});}
}
for (int i = 0; i < n; i++)
for (auto j : nums[i])
{
for (auto I : who[j])
{
g[idr[i][j]].pb({idr[I][j], abs(x[i] - x[I])});
g[idr[I][j]].pb({idr[i][j], abs(x[i] - x[I])});
}
who[j].pb(i);
}
while (sz(str))
{
pair <ll, int> pt = *str.begin(); str.erase(str.begin());
if (mk[pt.S] == 'b') continue;
mk[pt.S] = 'b';
if (pt.F >= ans) return ans;
auto it = se.upper_bound(ptr(pt.S, 1e9 + 1e9));
if (it != se.begin())
{
it--;
if ((*it).F == pt.S) {ans = min(ans, pt.F + (*it).S); se.erase(it); if (sz(se) == 0) return ans;}
}
for (auto it : g[pt.S])
{
ll s = pt.F + it.S;
if (dst[it.F] != - 1 && dst[it.F] <= s) continue;
if (ans <= s) continue;
dst[it.F] = s;
str.insert({s, it.F});
}
}
if (ans == 1e18) return -1;
return ans;
}
