#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 100005
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> pt;
vector <vector <pair <int, int> > > g;
vector <int> nums[N], who[N], db[N], del[N];
vector <ll> dst;
gp_hash_table <int, int> dob;
gp_hash_table <int, gp_hash_table <int, int> > idr;
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int to)
{
if (s == to) return 0;
int n = sz(x);
int m = sz(l);
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(pt(h[i], 1e9));
if (it != st.begin())
{
it--;
while (1)
{
who[(*it).S].pb(i);
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;
priority_queue <pair <ll, int> > qr;
set <int> se; se.clear();
for (int i = 0; i < n; i++)
for (auto j : nums[i])
{
if (i == to) {se.insert(id); dob[id] = y[j];}
idr[i][j] = id++;
g.emplace_back();
dst.emplace_back();
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 (s == i) {dst[id - 1] = 0; qr.push({-y[j], id - 1});}
}
fill(dst.begin(), dst.end(), -1);
for (int i = 0; i < n; i++)
for (auto j : nums[i])
for (auto I : who[j])
{
if (I == i) continue;
g[idr[i][j]].pb({idr[I][j], abs(x[i] - x[I])});
}
// while (sz(qr))
// {
// pair <ll, int> pt = qr.top(); qr.pop();
//
// if (se.find(pt.S) != se.end()) ans = min(ans, -pt.F + dob[pt.S]);
//
// for (auto itr : g[pt.S])
// {
// ll s = -pt.F + itr.S;
//
// if (dst[itr.F] != -1 && dst[itr.F] <= s) continue;
//
// dst[itr.F] = s;
//
// qr.push({-s, itr.F});
// }
// }
if (ans == 1e18) return -1;
return ans;
}
