#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;
ll st[20][100005];
int lg[100005];
void calc(int n){
lg[0]=lg[1]=0;
for(int i=2;i<=100000;i++) lg[i]=lg[(i>>1)]+1;
for(int i=1;i<=18;i++)
for(int j=0;j<n;j++)
st[i][j]=max(st[i-1][j], st[i-1][min(j+(1<<(i-1)), n)]);
}
ll getMax(int l, int r){
int pot=lg[r-l+1];
return max(st[pot][l], st[pot][r-(1<<pot)+1]);
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
int n=(int)x.size(), m=(int)l.size();
for(int i=0;i<n;i++) st[0][i]=h[i];
calc(n);
map<pii, ll> dist;
dist[{s, 0}]=0;
vector<vector<int>> proc(n);
proc[s].pb(0); proc[g].pb(0);
map<pii, vector<pii>> adj;
for(int i=0;i<m;i++){
int curr=l[i];
while(curr!=r[i]){
int low=curr+1, high=r[i]-1, best=r[i];
while(low<=high){
int mid=(low+high)>>1;
if(getMax(curr+1, mid)>=y[i]){
best=mid;
high=mid-1;
}
else low=mid+1;
}
proc[curr].pb(y[i]);
proc[best].pb(y[i]);
//~ cout << "added: " << curr << " -> " << best << " at " << y[i] << "\n";
adj[{curr, y[i]}].pb({best, y[i]});
adj[{best, y[i]}].pb({curr, y[i]});
curr=best;
}
}
for(int i=0;i<n;i++) sort(all(proc[i]));
for(int i=0;i<n;i++){
for(int j=1;j<(int)proc[i].size();j++)
adj[{i, proc[i][j-1]}].pb({i, proc[i][j]}), adj[{i, proc[i][j]}].pb({i, proc[i][j-1]});
}
priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<>> pq;
pq.push({0ll, {s, 0}});
while(!pq.empty()){
ll d=pq.top().fi;
int id=pq.top().se.fi, alt=pq.top().se.se;
pq.pop();
if(dist[{id, alt}]<d) continue;
for(auto u : adj[{id, alt}]){
if(dist.find(u)==dist.end() || dist[u]>d+(ll)(abs(u.se-alt)+abs(x[u.fi]-x[id]))){
dist[u]=d+(ll)(abs(u.se-alt)+abs(x[u.fi]-x[id]));
pq.push({dist[u], u});
}
}
}
if(dist.find({g, 0})==dist.end()) return -1;
return dist[{g, 0}];
}
