#include "walk.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector <int> arr;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int MAXN = 1e5+5, MAXT = 18e5+5;
const ll INF = 1e18;
int N, M, S[2], T;
ll dist[MAXT];
pii SY[MAXN];
arr Y, in[MAXN], out[MAXN];
map <int,int> ver[MAXN], hor[MAXN];
vector <pii> adj[MAXT];
set <pii> sky;
priority_queue <pli,vector<pli>,greater<pli> > PQ;
int get(int x,int y) {
int &p = ver[x][y];
if (!p) {
T++;
p = T;
}
return p;
}
int gethor(int id,int x) {
int &p = hor[id][x];
if (!p) {
p = get(x,Y[id]);
}
return p;
}
ll min_distance(arr X,arr H,arr L,arr R,arr YY,int st,int fn) {
Y = YY;
N = X.size();
M = Y.size();
S[0] = st;
S[1] = fn;
get(st,0);
get(fn,0);
for (int i=0;i<M;i++) {
in[L[i]].push_back(i);
out[R[i]].push_back(i);
gethor(i,L[i]);
gethor(i,R[i]);
SY[i] = {Y[i],i};
}
sort(SY,SY+M);
for (int t=0;t<2;t++) {
int l = S[t], r = S[t];
for (int i=0;i<M;i++) {
int x = SY[i].se;
int y = SY[i].fi;
if (S[t] <= L[x] || S[t] >= R[x]) continue;
while (H[l] < y) l--;
while (H[r] < y) r++;
gethor(x,l);
gethor(x,r);
}
}
for (int i=1;i<N-1;i++) {
for (int x : in[i-1]) {
sky.insert({Y[x],x});
}
for (int x : out[i]) {
sky.erase({Y[x],x});
}
set <int> cand;
for (auto x : ver[i]) {
auto y = sky.lower_bound({x.fi+1,0});
if (y != sky.end() && y->fi <= H[i]) {
cand.insert(y->se);
}
if (y == sky.begin()) continue;
y--;
if (y->fi == x.fi) {
if (y == sky.begin()) continue;
y--;
}
cand.insert(y->se);
}
for (auto x : cand) {
gethor(x,i);
}
}
for (int i=0;i<M;i++) {
pii last = {-1,-1};
for (auto x : hor[i]) {
if (last.fi != -1) {
int d = X[x.fi]-X[last.fi];
adj[x.se].push_back({last.se,d});
adj[last.se].push_back({x.se,d});
}
last = x;
}
}
for (int i=0;i<N;i++) {
pii last = {-1,-1};
for (auto x : ver[i]) {
if (last.fi != -1) {
int d = x.fi-last.fi;
adj[x.se].push_back({last.se,d});
adj[last.se].push_back({x.se,d});
}
last = x;
}
}
PQ.push({0,1});
for (int i=2;i<=T;i++) {
dist[i] = INF;
}
while (!PQ.empty()) {
pli x = PQ.top();
PQ.pop();
if (dist[x.se] != x.fi) continue;
for (pii y : adj[x.se]) {
if (dist[y.fi] <= x.fi + y.se) continue;
dist[y.fi] = x.fi + y.se;
PQ.push({dist[y.fi],y.fi});
}
}
if (dist[2] == INF) {
return -1;
}
return dist[2];
}
