#include "walk.h"
#include <algorithm>
#include <queue>
#include <tuple>
#define fs first
#define se second
using namespace std;
typedef long long llong;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
int n, m;
int X[100001], H[100001];
int L[100001], R[100001], Y[100001];
llong dijkstra(int s, int e, const vector<vector<pii>> &edge) {
const llong inf = 1e18;
int n = int(edge.size()) - 1;
vector<llong> D(n + 1, inf);
priority_queue<pll> pq;
D[s] = 0;
pq.emplace(0, s);
while (!pq.empty()) {
llong x, d;
tie(d, x) = pq.top();
pq.pop();
d = -d;
if (D[x] != d) continue;
for (pii i : edge[x]) {
llong nd = d + i.se;
if (nd < D[i.fs]) {
D[i.fs] = nd;
pq.emplace(-nd, i.fs);
}
}
}
return D[e] < inf ? D[e] : -1;
}
llong solve12(int s, int e) {
int idx = n;
vector<vector<pii>> P(n + 1);
vector<int> S[20];
for (int i = 0; i < 20; ++i) S[i] = vector<int>(n + 1);
for (int i = 1; i <= n; ++i) {
P[i].emplace_back(0, i);
S[0][i] = H[i];
}
for (int i = 1; i < 20; ++i) {
for (int j = 1; j <= n; ++j) {
S[i][j] = S[i - 1][j];
int k = j + (1 << i - 1);
if (k <= n) S[i][j] = max(S[i][j], S[i - 1][k]);
}
}
for (int i = 1; i <= m; ++i) {
for (int j = L[i]; j <= R[i]; ++j) {
if (Y[i] > H[j]) continue;
P[j].emplace_back(Y[i], ++idx);
}
}
vector<vector<pii>> edge(idx + 1);
auto add_edge = [&](int a, int b, int c) {
edge[a].emplace_back(b, c);
edge[b].emplace_back(a, c);
};
for (int i = 1; i <= n; ++i) {
sort(P[i].begin(), P[i].end());
for (int j = 1; j < int(P[i].size()); ++j) {
add_edge(P[i][j - 1].se, P[i][j].se, P[i][j].fs - P[i][j - 1].fs);
}
}
for (int i = 1; i <= m; ++i) {
int pri = -1, prx;
for (int j = L[i]; j <= R[i]; ++j) {
if (Y[i] > H[j]) continue;
int it = lower_bound(P[j].begin(), P[j].end(), pii(Y[i], 0))->se;
if (pri != -1) add_edge(pri, it, X[j] - prx);
pri = it;
prx = X[j];
if (j == R[i]) break;
for (int k = 20; k--; ) {
if (S[k][j + 1] < Y[i]) j += 1 << k;
}
}
}
return dijkstra(s, e, edge);
}
llong solve34() {
return -1;
}
llong 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();
for (int i = 1; i <= n; ++i) {
X[i] = x[i - 1];
H[i] = h[i - 1];
}
for (int i = 1; i <= m; ++i) {
L[i] = l[i - 1] + 1;
R[i] = r[i - 1] + 1;
Y[i] = y[i - 1];
}
if (s == 0 && g == n - 1) {
//return solve34();
}
return solve12(s + 1, g + 1);
}
