#include "walk.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
long long min_distance(vector<int> a, vector<int> h, vector<int> l, vector<int> r, vector<int> b, int S, int T){
int n = a.size(), m = l.size();
vector<int> ord(n), dt(m);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](auto x, auto y){
return h[x] > h[y];
});
iota(dt.begin(), dt.end(), 0);
sort(dt.begin(), dt.end(), [&](auto x, auto y){
return b[x] > b[y];
});
set<int> st;
map<pair<int, int>, int> mp;
auto idx = [&](int x, int y) -> int {
if (mp.find(make_pair(x, y)) == mp.end())
return mp[make_pair(x, y)] = mp.size();
return mp[make_pair(x, y)];
};
vector<vector<pair<int, int>>> g;
vector<vector<int>> pos(n);
{
int j = 0;
for (int &i: dt){
while (j < n && h[ord[j]] >= b[i]){
st.insert(ord[j]);
j++;
}
// cerr << ":::" << endl;
auto it = st.lower_bound(l[i]);
// cerr << *it << endl;
while (it != st.end() && *it != r[i]){
auto it2 = it;
it++;
int u = idx(*it2, b[i]), v = idx(*it, b[i]);
pos[*it2].push_back(b[i]);
pos[*it].push_back(b[i]);
g.resize(mp.size());
g[u].emplace_back(v, a[*it] - a[*it2]);
g[v].emplace_back(u, a[*it] - a[*it2]);
}
}
}
// cerr << "OK" << endl;
idx(S, 0), idx(T, 0);
// cerr << idx(S, 0) << ' ' << idx(T, 0) << endl;
pos[S].push_back(0);
pos[T].push_back(0);
// cerr << endl;
// for (int i = 0; i < n; i++)
// cerr << pos[i].size() << ' ';
// cerr << endl;
for (int i = 0; i < n; i++){
for (int j = 0; j < (int)pos[i].size() - 1; j++){
int u = idx(i, pos[i][j]), v = idx(i, pos[i][j + 1]);
// cerr << u << ' ' << v << endl;
g.resize(mp.size());
g[u].emplace_back(v, pos[i][j] - pos[i][j + 1]);
g[v].emplace_back(u, pos[i][j] - pos[i][j + 1]);
}
}
// cerr << "OK2" << endl;
int N = g.size();
// for (int i = 0; i < N; i++)
// for (auto &[v, w]: g[i])
// cerr << i << ' ' << v << ' ' << w << endl;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
vector<bool> vis(N);
vector<long long> dis(N, INF);
pq.emplace(0, idx(S, 0));
dis[idx(S, 0)] = 0;
while (pq.size()){
auto [d, u] = pq.top();
pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto &[v, w]: g[u]){
if (dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
pq.emplace(dis[v], v);
}
}
}
// cerr << endl << g[idx(S, 0)].size() << endl;
// for (int i = 0; i < N; i++)
// cerr << dis[i] << ' ';
// cerr << endl;
long long ans = dis[idx(T, 0)];
return ans >= INF? -1: ans;
}
