#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int e){
ll n=x.size(), m=l.size();
map<pair<ll,ll>,vector<pair<ll,ll>>> g;
// for(ll i=0; i<m; i++){
// ll prev=x[l[i]];
// for(ll j=l[i]+1; j<=r[i]; j++){
// if(y[i]<=h[j]){
// pair<ll,ll> u={y[i],prev}, v={y[i],x[j]};
// g[u].push_back(v);
// g[v].push_back(u);
// // cout<<u.first<<","<<u.second<<" - "<<v.first<<","<<v.second<<endl;
// prev=x[j];
// }
// }
// }
vector<ll> b[n], w[m];
for(ll i=0; i<n; i++){
b[i].push_back(0);
for(ll j=0; j<m; j++){
if(l[j]<=i && i<=r[j] && y[j]<=h[i]){
b[i].push_back(y[j]);
w[j].push_back(x[i]);
}
}
}
for(ll i=0; i<n; i++){
sort(b[i].begin(),b[i].end());
for(ll j=1; j<b[i].size(); j++){
pair<ll,ll> u={b[i][j-1],x[i]}, v={b[i][j],x[i]};
g[u].push_back(v);
g[v].push_back(u);
}
}
for(ll i=0; i<m; i++){
sort(w[i].begin(),w[i].end());
for(ll j=1; j<w[i].size(); j++){
pair<ll,ll> u={y[i],w[i][j-1]}, v={y[i],w[i][j]};
g[u].push_back(v);
g[v].push_back(u);
}
}
map<pair<ll,ll>,ll> dist; dist[{0,x[s]}]=0;
map<pair<ll,ll>,bool> vis;
priority_queue<pair<ll,pair<ll,ll>>> q; q.push({0,{0,x[s]}});
while(!q.empty()){
pair<ll,ll> curr=q.top().second;
q.pop();
if(vis[curr]) continue;
vis[curr]=1;
// cout<<curr.first<<" "<<curr.second<<" "<<dist[curr]<<endl;
for(auto nxt:g[curr]){
ll y=abs(curr.first-nxt.first)+abs(curr.second-nxt.second);
if(dist.find(nxt)==dist.end() || dist[nxt]>dist[curr]+y){
dist[nxt]=dist[curr]+y;
q.push({-dist[nxt],nxt});
}
}
}
if(vis[{0,x[e]}]) return dist[{0,x[e]}];
else return -1;
}
