#pragma GCC optimize("O3")
#include "walk.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
const ll inf=(ll)1e18;
}
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) {
auto st=clock();
int n=(int)x.size();
int m=(int)l.size();
vector<vector<int>> ys(n);
for(int i=0;i<n;i++){
ys[i].push_back(0);
}
for(int i=0;i<m;i++){
for(int j=l[i];j<=r[i];j++){
if(y[i]<=h[j]){
ys[j].push_back(y[i]);
}
}
}
vector<vector<int>> id(n);
int cnt=0;
for(int i=0;i<n;i++){
sort(all(ys[i]));
ys[i].resize(unique(all(ys[i]))-ys[i].begin());
id[i].resize(ys[i].size());
for(int j=0;j<(int)id[i].size();j++){
id[i][j]=cnt++;
}
}
vector<vector<pair<int,int>>> adj(cnt);
auto add_edge=[&](int a,int b,int c){
adj[a].push_back({b,c});
adj[b].push_back({a,c});
};
for(int i=0;i<n;i++){
for(int j=0;j<(int)ys[i].size()-1;j++){
add_edge(id[i][j],id[i][j+1],ys[i][j+1]-ys[i][j]);
}
}
for(int i=0;i<m;i++){
vector<pair<int,int>> tmp;
for(int j=l[i];j<=r[i];j++){
if(y[i]<=h[j]){
int pos=lower_bound(all(ys[j]),y[i])-ys[j].begin();
tmp.push_back({j,id[j][pos]});
}
}
for(int j=0;j<(int)tmp.size()-1;j++){
add_edge(tmp[j].s,tmp[j+1].s,x[tmp[j+1].f]-x[tmp[j].f]);
}
}
vector<ll> d(cnt,inf);
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
d[id[s][0]]=0;
pq.push({0,id[s][0]});
int en=id[g][0];
while(!pq.empty() and clock()-st<3.8*CLOCKS_PER_SEC){
auto v=pq.top();
pq.pop();
if(v.f!=d[v.s]) continue;
if(v.s==en) return v.f;
for(auto u:adj[v.s]){
if(clock()-st>3.8*CLOCKS_PER_SEC) break;
if(d[v.s]+u.s<d[u.f]){
d[u.f]=d[v.s]+u.s;
pq.push({d[u.f],u.f});
}
}
}
return -1;
}
