#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 g){
int n = x.size();
int m = l.size();
vector<vector<pair<int,int>>> points(n);
vector<vector<pair<int,int>>> adj(n);
int S = n;
for(int i=0;i<n;i++)points[i].emplace_back(i,0);
vector<tuple<int,int,int>> skywalks;
for(int i=0;i<m;i++)skywalks.emplace_back(y[i],l[i],r[i]);
sort(skywalks.begin(), skywalks.end());
auto add_point = [&](int x,int h) {
adj.emplace_back();
adj[S].emplace_back(points[x].back().first,h-points[x].back().second);
adj[points[x].back().first].emplace_back(S,h-points[x].back().second);
points[x].emplace_back(S,h);
return S++;
};
for(int i=0;i<m;i++){
auto [height,left,right] = skywalks[i];
auto last_point = add_point(left,height);
auto last_x = x[left];
for(int j=left+1;j<=right;j++) {
if(h[j]<height)continue;
auto curr_point = add_point(j,height);
adj[curr_point].emplace_back(last_point,x[j]-last_x);
adj[last_point].emplace_back(curr_point,x[j]-last_x);
last_point=curr_point;
last_x=x[j];
}
}
priority_queue<pair<long long,int>> q;
vector<bool> visited(S);
q.emplace(0,s);
while(!q.empty()) {
auto [dist,idx] = q.top();q.pop();dist=-dist;
if(visited[idx])continue;
visited[idx]=true;
if(idx==g)return dist;
for(auto&[v,c]:adj[idx])if(!visited[v])q.emplace(-dist-c,v);
}
return -1;
}
