#include "walk.h"
#include<bits/stdc++.h>
#define ll long long
#define sz(v) (int)(v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
using namespace std;
const int inf=1e9+7;
const ll INF=1e16;
const int maxn=1e5+10;
int L[maxn], R[maxn];
ll dist[10*maxn];
vector<pii>expand[maxn];
vector<pii>adj[10*maxn];
void dijkstra(int x, int n){
for(int i=0;i<n;i++) dist[i]=INF;
dist[x]=0;
set<pll>s;
for(int i=0;i<n;i++) s.insert({dist[i],i});
while(s.size()){
auto f=s.begin();
int u=f->se;
s.erase(f);
for(pii p : adj[u]){
int viz=p.fi;
ll cost=p.se;
// cout << "! " << u << " -> " << viz << ' ' << cost << '\n';
if(dist[u]+cost<dist[viz]){
s.erase({dist[viz],viz});
dist[viz]=dist[u]+cost;
s.insert({dist[viz],viz});
}
}
}
}
void remove(int x){
R[L[x]]=R[x];
L[R[x]]=L[x];
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
int n=sz(x), m=sz(l);
vector<pair<int,pii>>ord;
for(int i=0;i<m;i++) ord.push_back({y[i],{l[i],r[i]}});
sort(ord.begin(),ord.end());
vector<pii>ativar;
for(int i=0;i<n;i++) ativar.push_back({h[i],i});
sort(ativar.begin(),ativar.end()); reverse(ativar.begin(),ativar.end());
for(int i=1;i<n;i++) L[i]=i-1;
for(int i=0;i<n;i++) R[i]=i+1;
for(int i=0;i<n;i++) expand[i].push_back({0,i});
int ini=0, fim=n-1, cnt=n;
for(pair<int,pii> p : ord){
while(sz(ativar)&&ativar.back().fi<p.fi){
remove(ativar.back().se);
ativar.pop_back();
}
int at=p.se.fi, last=-1;
// cout << "andar: ";
while(at<=p.se.se){
// cout << at << ' ';
if(expand[at].back().fi!=p.fi){
adj[expand[at].back().se].push_back({cnt,p.fi-expand[at].back().fi});
adj[cnt].push_back({expand[at].back().se,p.fi-expand[at].back().fi});
expand[at].push_back({p.fi,cnt});
cnt++;
}
if(last!=-1){
int a=expand[last].back().se, b=expand[at].back().se;
adj[a].push_back({b,x[at]-x[last]});
adj[b].push_back({a,x[at]-x[last]});
}
last=at;
at=R[at];
}
// cout << '\n';
}
dijkstra(s,cnt);
// for(int i=0;i<cnt;i++) cout << dist[i] << ' ';
// cout << '\n';
if(dist[g]==INF) return -1;
return dist[g];
}
