#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifndef WAIMAI
#include "walk.h"
#else
#include "grader.cpp"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1e5 + 5;
int n, m, s, e, sz;
vector<int> y[SIZE];
int x[SIZE], h[SIZE];
vector<pair<int, int>> P, Q;
tuple<int, int, int> a[SIZE];
int get_id(int i, int y) {
return lower_bound(P.begin(), P.end(), make_pair(i, y)) - P.begin() + 1;
}
set<pair<int, int>> seg;
void split(int p) {
auto it = prev(seg.lower_bound({p + 1, 0}));
if (it->F != p) seg.emplace(p, it->S);
}
void upd(int l, int r, int y) {
split(l), split(r + 1);
for (auto it = seg.lower_bound({l, 0}); it->F <= r; it = seg.erase(it));
seg.emplace(l, y);
}
int get_h(int p) {
auto it = prev(seg.lower_bound({p + 1, 0}));
return it->S;
}
ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g) {
n = _x.size(), m = _l.size();
s = _s + 1, e = _g + 1;
FOR (i, 1, n) {
x[i] = _x[i - 1];
h[i] = _h[i - 1];
}
FOR (i, 1, m) {
_l[i - 1]++, _r[i - 1]++;
a[i] = {_y[i - 1], _l[i - 1], _r[i - 1]};
}
seg.emplace(1, 0);
seg.emplace(n + 1, 0);
sort(a + 1, a + m + 1);
FOR (i, 1, n) y[i].pb(0);
FOR (i, 1, m) {
auto [h, l, r] = a[i];
y[l].pb(h), y[r].pb(h);
y[l].pb(get_h(l));
y[r].pb(get_h(r));
upd(l, r, h);
}
seg.clear();
seg.emplace(1, inf);
seg.emplace(n + 1, inf);
for (int i = m; i >= 1; i--) {
auto [h, l, r] = a[i];
int hl = get_h(l), hr = get_h(r);
if (hl != inf) y[l].pb(hl);
if (hr != inf) y[r].pb(hr);
upd(l, r, h);
}
FOR (i, 1, n) {
sort(y[i].begin(), y[i].end());
y[i].erase(unique(y[i].begin(), y[i].end()), y[i].end());
for (int iy : y[i]) P.pb(i, iy), Q.pb(iy, i);
sz += y[i].size();
}
sort(Q.begin(), Q.end());
vector<ll> dis(sz + 1, INF);
vector<vector<pair<int, int>>> adj(sz + 1);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
FOR (i, 1, n) for (int j = 0; j + 1 < y[i].size(); j++) {
int u = get_id(i, y[i][j]), v = get_id(i, y[i][j + 1]);
adj[u].pb(v, y[i][j + 1] - y[i][j]);
adj[v].pb(u, y[i][j + 1] - y[i][j]);
}
FOR (i, 1, m) {
auto [h, l, r] = a[i];
int j = lower_bound(Q.begin(), Q.end(), make_pair(h, l)) - Q.begin();
while (Q[j].S < r) {
int u = get_id(Q[j].S, h), v = get_id(Q[j + 1].S, h), d = x[Q[j + 1].S] - x[Q[j].S];
adj[u].pb(v, d);
adj[v].pb(u, d);
j++;
}
}
s = get_id(s, 0), e = get_id(e, 0);
pq.emplace(dis[s] = 0, s);
while (pq.size()) {
auto [d, pos] = pq.top();
pq.pop();
if (d > dis[pos]) continue;
for (auto [np, w] : adj[pos]) if (d + w < dis[np]) {
pq.emplace(dis[np] = d + w, np);
}
}
return dis[e] == INF ? -1 : dis[e];
}
/*
in1
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
out1
27
in2
5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4
out2
21
*/
