#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int e) {
int n = x.size();
int m = y.size();
map<array<int,2>,vector<array<int,2>>>g;
set<array<int,2>>pts;
for(int i = 0;i<m;i++){
array<int,2>las={-1,-1};
for(int j = l[i];j<=r[i];j++){
if(h[j]<y[i])
continue;
//intersection found (x[j],y[i])
if(las[0]!=-1)
g[{x[j],y[i]}].push_back(las);
las={x[j],y[i]};
pts.insert({x[j],y[i]});
}
las={-1,-1};
for(int j = r[i];j>=l[i];j--){
if(h[j]<y[i])
continue;
//intersection found (x[j],y[i])
if(las[0]!=-1)
g[{x[j],y[i]}].push_back(las);
las={x[j],y[i]};
pts.insert({x[j],y[i]});
}
}
array<int,2>las={-1,-1};
pts.insert({x[s],0});
pts.insert({x[e],0});
for(array<int,2>a:pts){
if(a[0]==las[0]){
//same coordinate, must connect.
g[a].push_back(las);
g[las].push_back(a);
}
las=a;
}
priority_queue<pair<long long,array<int,2>>,vector<pair<long long,array<int,2>>>,greater<pair<long long,array<int,2>>>>pq;
pq.push({0,{x[s],0}});
map<array<int,2>,long long>dists;
while(pq.size()){
pair<long long,array<int,2>>p = pq.top();
pq.pop();
if(dists.find(p.second)!=dists.end()&&dists[p.second]<=p.first)
continue;
dists[p.second]=p.first;
for(array<int,2>e:g[p.second]){
pq.push({p.first+abs(e[0]-p.second[0])+abs(e[1]-p.second[1]),e});
}
}
if(dists.find({x[e],0})==dists.end()){
return -1;
}
return dists[{x[e],0}];
}
