#include <bits/stdc++.h>
#include "walk.h"
#define MAX 100000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vi;
ll dist[1000010];
ll isq[1000010];
vector<vi> G;
void dijktra(ll u){
memset(isq,0,sizeof isq);
for(int i=0;i<=1000010;i++){
dist[i]=MAX;
}
priority_queue<ii,vi,greater<ii> > pq;
dist[u]=0;
isq[u]=1;
pq.push(ii(0,u));
while(!pq.empty()){
int x=pq.top().second;
int di=pq.top().first;
pq.pop();
isq[x]=0;
if(di>dist[x]) continue;
for(auto &v:G[x]){
int w=v.first;
if(dist[v.second]>dist[x]+w){
dist[v.second]=dist[x]+w;
if(isq[v.second]==0){
pq.push(ii(dist[v.second],v.second));
isq[v.second]=1;
}
}
}
}
}
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) {
ll no;
no=0;
map<ii,int> m;
for(int i=0;i<x.size();i++){
no++;
m[ii(x[i],0)]=no;
//printf("(%d,%d) %lld\n",x[i],0,no);
}
//cout<<endl;
G.resize(1000000);
for(int i=0;i<y.size();i++){
int ant=-1,id;
for(int j=l[i];j<=r[i];j++){
if(h[j]>=y[i]){
if(m[ii(x[j],y[i])]==0){
no++;
m[ii(x[j],y[i])]=no;
//printf("(%d,%d) %lld\n",x[j],y[i],no);
}
if(ant==-1){
ant=m[ii(x[j],y[i])];
id=j;
}
else{
int dis=abs(x[j]-x[id]);
int u=m[ii(x[j],y[i])];
G[ant].push_back(ii(dis,u));
G[u].push_back(ii(dis,ant));
ant=u;
id=j;
}
}
}
}
for(int i=0;i<x.size();i++){
int ant=0;
for(int j=1;j<=h[i];j++){
if(m[ii(x[i],j)]!=0){
int u=m[ii(x[i],j)];
int v=m[ii(x[i],ant)];
int w=abs(ant-j);
G[u].push_back(ii(w,v));
G[v].push_back(ii(w,u));
ant=j;
}
}
}
/*for(int i=0;i<26;i++){
cout<<i<<" : ";
for(int j=0;j<G[i].size();j++){
cout<<"("<<G[i][j].second<<", "<<G[i][j].first<<") ";
}
cout<<endl;
}*/
dijktra(m[ii(x[s],0)]);
return dist[m[ii(x[g],0)]];
}
