#include "walk.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
using namespace std;
const int MAX=1e5+5;
const ll INF=1LL<<60;
struct ST{
ll s,e,m,d;
ST *l=0,*r=0;
ll p0=-INF,p1=INF,v=0; // set, min
ST(ll s,ll e):s(s),e(e),m((s+e)/2),d(e-s+1){
if (d==1) return;
}
void cc(){
if (d==1) return;
if (!l) l=new ST(s,m);
if (!r) r=new ST(m+1,e);
}
void apl(ll a0,ll a1){
if (a0!=-INF) p0=a0,p1=INF,v=a0;
a1=min(p1,a1),v=min(v,a1);
}
void down(){
if (d>1) l->apl(p0,p1),r->apl(p0,p1);
p0=-INF,p1=INF;
}
ll qry(int x){
if (d==1) return v;
cc();
down();
if (x>m) return r->qry(x);
else return l->qry(x);
}
void upd(int x,int y,ll a0,ll a1){
if (y<x||y<s||x>e) return;
if (x<=s&&y>=e) return apl(a0,a1);
cc();
down();
l->upd(x,y,a0,a1),r->upd(x,y,a0,a1);
}
void upd0(int x,int y,ll a){
upd(x,y,a,INF);
}
void upd1(int x,int y,ll a){
upd(x,y,-INF,a);
}
};
int N,M;
priority_queue<pair<ll,pii>,vector<pair<ll,pii>>,greater<>> pq;
map<pii,ll> dst;
map<pii,vector<pair<ll,pii>>> adj;
vector<ll> hs[MAX];
long long min_distance(vector<int> X,vector<int> H,vector<int> L,vector<int> R,vector<int> Y,int S,int E) {
N=X.size(),M=L.size();
for (int i=0;i<M;i++) for (int x=L[i];x<=R[i];x++) if (Y[i]<=H[x]) hs[x].push_back(Y[i]);
hs[S].push_back(0),hs[E].push_back(0);
for (int i=0;i<N;i++) sort(hs[i].begin(),hs[i].end());
for (int i=0;i<N;i++) for (int x=0;x<hs[i].size()-1;x++){
pii a={i,x};
pii b={i,x+1};
ll w=hs[i][x+1]-hs[i][x];
adj[a].push_back({w,b}),adj[b].push_back({w,a});
}
for (int i=0;i<M;i++){
int p=lower_bound(hs[L[i]].begin(),hs[L[i]].end(),Y[i])-hs[L[i]].begin();
for (int x=L[i]+1;x<=R[i];x++){
int j=lower_bound(hs[x].begin(),hs[x].end(),Y[i])-hs[x].begin();
if (p<hs[x-1].size()&&j<hs[x].size()){
pii a={x-1,p};
pii b={x,j};
ll w=X[x]-X[x-1];
adj[a].push_back({w,b}),adj[b].push_back({w,a});
}
p=j;
}
}
pq.push({0,{S,0}});
while (pq.size()){
auto [d,pr]=pq.top();
pq.pop();
if (dst.count(pr)&&d>=dst[pr]) continue;
dst[pr]=d;
for (auto [w,qr]:adj[pr]){
pq.push({d+w,qr});
}
}
pii ep={E,0};
if (dst.count(ep)) return dst[ep];
return -1;
}
