#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
struct edge{
int to_x,to_y;
int dist;
};
vector<int>node[100000];
vector<vector<edge>>e[100000];
vector<long long>dist[100000];
long long min_distance(vector<int>x,vector<int>h,vector<int>l,vector<int>r,vector<int>y,int s,int g){
int N,M;
N=x.size();
M=l.size();
for(int i=0;i<N;i++){
node[i].push_back(0);
node[i].push_back(h[i]);
}
for(int i=0;i<M;i++){
for(int j=l[i];j<=r[i];j++){
if(h[j]>=y[i]){
node[j].push_back(y[i]);
}
}
}
for(int i=0;i<N;i++){
sort(node[i].begin(),node[i].end());
node[i].erase(unique(node[i].begin(),node[i].end()),node[i].end());
dist[i]=vector<long long>(node[i].size(),-1);
e[i]=vector<vector<edge>>(node[i].size());
for(int j=0;j<node[i].size()-1;j++){
e[i][j].push_back({i,j+1,node[i][j+1]-node[i][j]});
e[i][j+1].push_back({i,j,node[i][j+1]-node[i][j]});
}
}
for(int i=0;i<M;i++){
vector<pair<int,int>>p;
for(int j=l[i];j<=r[i];j++){
if(h[j]>=y[i]){
p.push_back({j,lower_bound(node[j].begin(),node[j].end(),y[i])-node[j].begin()});
}
}
for(int j=0;j<p.size()-1;j++){
e[p[j].first][p[j].second].push_back({p[j+1].first,p[j+1].second,x[p[j+1].first]-x[p[j].first]});
e[p[j+1].first][p[j+1].second].push_back({p[j].first,p[j].second,x[p[j+1].first]-x[p[j].first]});
}
}
priority_queue<pair<long long,pair<int,int>>,vector<pair<long long,pair<int,int>>>,greater<pair<long long,pair<int,int>>>>pq;
pq.push({0,{s,0}});
while(!pq.empty()){
long long l;
int px;
int py;
l=pq.top().first;
px=pq.top().second.first;
py=pq.top().second.second;
pq.pop();
if(dist[px][py]==-1){
dist[px][py]=l;
for(edge E:e[px][py]){
pq.push({l+E.dist,{E.to_x,E.to_y}});
}
}
}
return dist[g][0];
}
