#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
const int N = 2e6+100, K = 20, M=2E5;
int n, m;
map<pair<int, int>, int> node;
vector<pair<int,int>> G[N];
vector<int> F[N];
vector<pair<int, ll>> g[N];
int rmq[M][K];
int get(int l, int r){
int k = log2(r-l+1);
return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int gg) {
n = x.size();
m = l.size();
for(int i = 0; i < m; ++i){
int u = l[i], v = r[i], L = y[i];
F[u].pb(L);
F[v].pb(L);
G[u].pb({v, L});
G[v].pb({u, L});
}
for(int i = 1; i <= n; ++i) rmq[i][0] = h[i - 1];
for(int j = 1; j < K ;++j){
for(int i = 1; i + (1<<j) <= n+1; ++i){
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j-1))][j-1]);
}
}
int co = 0;
for(int i = 0; i < n; ++i){
for(auto U: G[i]){
int u = U.ff; ll w = U.ss;
if(u > i){
if(node[{i,w}] == 0)
node[{i, w}] = co++;
int last = i;
while(last < u){
int l = last + 2, r = n, p = n + 1;
while(l <= r){
int mid = l+r>>1;
if(get(last + 2, mid) >= w){
p = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
--p;
if(h[p] >= w){
if(node[{p,w}]==0)
node[{p, w}] = co++;
// cout << x[p] << ' ' << x[last] << '\n';
g[node[{last, w}]].pb({node[{p,w}], abs(x[p] - x[last])});
g[node[{p,w}]].pb({node[{last, w}], abs(x[p] - x[last])});
F[p].pb(w);
}
last = p;
}
}
}
}
for(int i = 0; i < n; ++i){
F[i].pb(0);
// F[i].pb(h[i]);
sort(all(F[i]));
F[i].erase(unique(all(F[i])), F[i].end());
vector<int> X;
if(node[{i,0}]==0) node[{i, 0}] = co++;
// if(node[{i,h[i]}]==0) node[{i, 0}] = co++;
for(int p: F[i]){
// cout << i << ' ' <<p << '\n';
// node[{i, p}] = co++;
X.pb(node[{i, p}]);
}
for(int j = 0; j + 1 < F[i].size(); ++j){
// cout << F[i][j] << ' ';
g[X[j]].pb({X[j+1], F[i][j + 1] - F[i][j]});
g[X[j + 1]].pb({X[j], F[i][j + 1] - F[i][j]});
}
// cout << '\n';
}
// cout << "\n";
// for(int i = 0; i < n; ++i){
// for(auto U: G[i]){
// int u = U.ff; ll w = U.ss;
// if(u > i){
// int last = i;
// int j = u;
// g[node[{last, w}]].pb({node[{j, w}], abs(x[j]-x[last])});
// g[node[{j, w}]].pb({node[{last, w}], abs(x[j]-x[last])});
// last = j;
// }
// }
// }
vector<ll> dist(co, 1e15*1ll);
vector<bool> vis(co);
priority_queue<pair<ll, int>> Q;
Q.push({0, node[{s, 0}]});
dist[node[{s, 0}]] = 0;
while(!Q.empty()){
int v = Q.top().ss; Q.pop();
if(vis[v]) continue;
// cout << v << ' ' << dist[v] << '\n';
vis[v] = 1;
for(auto U: g[v]){
int u = U.ff;
ll w= U.ss;
if(dist[u] > dist[v] + w){
dist[u] = dist[v] + w;;
Q.push({-dist[u], u});
}
}
}
ll D = dist[node[{gg, 0}]];
if(D == 1e15*1ll) return -1;
// cout << node[{gg,0}] << ' ';
return D;
}
