#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
int get(int a, int b, int c, int d){
return abs(c - a) + abs(d - b);
}
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(), m = l.size();
map<int,vector<pair<int,int> > > adj[n];
vector<int> st[n], nd[n];
for(int i = 0; i < m; i++){
st[l[i]].push_back(y[i]);
nd[r[i]].push_back(y[i]);
}
set<pair<int,int> > hh;
for(int i = 0; i < n; i++){
set<pair<int,int> > nw;
while(hh.size() && hh.begin()->first <= h[i]){
nw.insert({hh.begin()->first,i});
adj[i][hh.begin()->first].push_back({hh.begin()->second,hh.begin()->first});
adj[hh.begin()->second][hh.begin()->first].push_back({i,hh.begin()->first});
hh.erase(hh.begin());
}
for(auto u:nw) hh.insert(u);
for(auto u:nd[i]) if(hh.lower_bound({u,0}) != hh.end()) hh.erase(hh.lower_bound({u,0}));
for(auto u:st[i]) hh.insert({u,i});
}
for(int i = 0; i < n; i++){
vector<int> add = {0};
for(auto u:adj[i]) add.push_back(u.first);
for(int j = 0; j < add.size() - 1; j++){
adj[i][add[j]].push_back({i, add[j + 1]});
adj[i][add[j + 1]].push_back({i, add[j]});
}
}
map<int,long long> dist[n];
dist[s][0] = 0;
priority_queue<pair<long long, pair<int,int> > > q;
q.push({0, {s, 0}});
while(q.size()){
auto tp = q.top();
q.pop();
tp.first *= -1;
long long cost = tp.first;
int a = tp.second.first, b = tp.second.second;
if(dist[a][b] != cost) continue;
if(a == g && b == 0) return cost;
for(auto u:adj[a][b]){
if(dist[u.first].count(u.second) == 0 || dist[u.first][u.second] > cost + get(x[a], b, x[u.first], u.second)){
dist[u.first][u.second] = cost + get(x[a], b, x[u.first], u.second);
q.push({-dist[u.first][u.second], u});
}
}
}
return -1;
}
