#include <bits/stdc++.h>
using namespace std;
#include "walk.h"
typedef long long ll;
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 g){
int n = x.size();
vector<ll> build_pts[n];
for (int i=0;i<n;i++){
build_pts[i].push_back(0);
}
map<pair<ll,ll>,vector<pair<ll,ll>>> out; // (x,y) -> (x,y)
for (int i=0;i<l.size();i++){
vector<pair<ll,ll>> pts;
for (int j=l[i];j<=r[i];j++){
if (y[i] <= h[j]){
pts.push_back({x[j],y[i]});
build_pts[j].push_back(y[i]);
}
}
for (int j=1;j<pts.size();j++){
out[pts[j]].push_back(pts[j-1]);
out[pts[j-1]].push_back(pts[j]);
}
}
for (int i=0;i<n;i++){
sort(build_pts[i].begin(),build_pts[i].end());
for (int j=1;j<build_pts[i].size();j++){
out[{x[i],build_pts[i][j-1]}].push_back({x[i],build_pts[i][j]});
out[{x[i],build_pts[i][j]}].push_back({x[i],build_pts[i][j-1]});
}
}
map<pair<ll,ll>,bool> vis;
map<pair<ll,ll>,ll> dist;
priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>, greater<pair<ll,pair<ll,ll>>>> prq;
prq.push({0,{x[s],0}});
while (prq.size()){
auto [d, v] = prq.top();
prq.pop();
if (vis[v]) continue;
vis[v] = 1;
dist[v] = d;
for (auto &u : out[v]){
if (!vis[u]){
prq.push({d + abs(u.first-v.first)+abs(u.second-v.second),u});
}
}
}
if (!vis[{x[g],0}]){
return -1;
} else {
return dist[{x[g],0}];
}
}
