// In the name of Allah
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 4;
const int maxs = 1e5 + 4;
const int maxlg = 20;
const ll oo = 1e18 + 4;
int sz, n, m;
vector<pll> adj[maxn];
vector<int> A[maxn], ls; pll val[maxn];
ll dis[maxn]; bool mark[maxn];
pii rmq[maxs][maxlg];
priority_queue<pll> qu;
void addE(int i, int j) {
ll w = abs(val[i].F - val[j].F) + abs(val[i].S - val[j].S);
adj[i].pb(Mp(j, w)); adj[j].pb(Mp(i, w));
}
int get_max(int l, int r) {
int j = __lg(r - l);
return max(rmq[l][j], rmq[r - (1 << j)][j]).S;
}
void get_val(int l, int r, ll x) {
if (r - l <= 0) return ;
int j = get_max(l, r);
if (rmq[j][0].F < x) return ;
ls.pb(j);
get_val(l, j, x); get_val(j + 1, r, x);
}
bool cmp(int i, int j) {
return (val[i].S < val[j].S);
}
void dij(int v) {
fill(dis, dis + sz, oo); fill(mark, mark + sz, 0);
dis[v] = 0; qu.push(Mp(-dis[v], v));
while (!qu.empty()) {
int v = qu.top().S; qu.pop();
if (mark[v]) continue;
mark[v] = 1;
for (auto f : adj[v]) {
int u = f.F; ll w = f.S;
if (dis[v] + w < dis[u]) {
dis[u] = dis[v] + w;
qu.push(Mp(-dis[u], u));
}
}
}
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
sz = 0; n = len(h); m = len(y);
int v1 = sz++;
val[v1] = Mp(x[s], 0); A[s].pb(v1);
int v2 = sz++;
val[v2] = Mp(x[g], 0); A[g].pb(v2);
for (int i = n - 1; i >= 0; i--) {
rmq[i][0] = Mp(h[i], i);
for (int j = 1; j < maxlg; j++) {
if (i + (1 << j) - 1 >= n) break;
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 0; i < m; i++) {
ls.clear();
get_val(l[i], r[i] + 1, y[i]);
sort(all(ls));
int vx = -1, ux = -1;
for (int j : ls) {
vx = sz++;
val[vx] = Mp(x[j], y[i]); A[j].pb(vx);
if (ux != -1) addE(ux, vx);
ux = vx;
}
}
for (int i = 0; i < n; i++) {
sort(all(A[i]), cmp);
for (int j = 1; j < len(A[i]); j++) {
addE(A[i][j - 1], A[i][j]);
}
}
dij(v1);
if (dis[v2] == oo) return -1;
else return dis[v2];
}
