#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e5+7;
vector<pair<ll,ll>>V[10*LIM];
set<pair<ll,ll>>S;
map<pair<ll,ll>,ll>mp;
ll tr[4*LIM], odl[10*LIM], n, N=1, akt;
void upd(int l, int r, ll x) {
l+=N; r+=N;
tr[l]=max(tr[l], x);
tr[r]=max(tr[r], x);
while(l/2!=r/2) {
if(l%2==0) tr[l+1]=max(tr[l+1], x);
if(r%2==1) tr[r-1]=max(tr[r-1], x);
l/=2; r/=2;
}
}
ll cnt(int v) {
v+=N;
ll ans=tr[v];
while(v) {
ans=max(ans, tr[v]);
v/=2;
}
return ans;
}
void kraw(pair<ll,ll>a, pair<ll,ll>b) {
if(mp.find(a)==mp.end()) {
mp[a]=akt++;
S.insert({a.nd, a.st});
}
if(mp.find(b)==mp.end()) {
mp[b]=akt++;
if(S.find({b.nd, b.st})==S.end() && b.nd!=0) {
auto it=S.lower_bound({b.nd, b.st});
if(it!=S.end()) {
auto x=*it;
if(x.st==b.nd) kraw(b, {x.nd, x.st});
}
if(it!=S.begin()) {
--it;
auto x=*it;
if(x.st==b.nd) kraw(b, {x.nd, x.st});
}
}
S.insert({b.nd, b.st});
}
ll o=abs(a.st-b.st)+abs(a.nd-b.nd);
V[mp[a]].pb({mp[b], o});
V[mp[b]].pb({mp[a], o});
}
ll min_distance(vector<int>x, vector<int>h, vector<int>l, vector<int>r, vector<int>y, int s, int g) {
n=x.size();
while(N<n) N*=2;
vector<pair<ll,pair<ll,ll>>>P;
rep(i, l.size()) P.pb({y[i], {l[i], r[i]}});
mp[{x[s], 0}]=0;
mp[{x[g], 0}]=1;
akt=2;
sort(all(P));
for(auto i : P) {
kraw({x[i.nd.st], i.st}, {x[i.nd.nd], i.st});
kraw({x[i.nd.st], i.st}, {x[i.nd.st], cnt(i.nd.st)});
kraw({x[i.nd.nd], i.st}, {x[i.nd.nd], cnt(i.nd.nd)});
upd(i.nd.st, i.nd.nd, i.st);
}
rep(i, akt+1) odl[i]=INF;
priority_queue<pair<ll,ll>>q;
q.push({0, 0});
while(!q.empty()) {
ll o=-q.top().st, p=q.top().nd; q.pop();
if(odl[p]<=o) continue;
odl[p]=o;
for(auto i : V[p]) q.push({-o-i.nd, i.st});
}
if(odl[1]==INF) return -1;
return odl[1];
}
