#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define int long long
int n;
vector<int> h;
vector<vector<int>> st;
bool comp(int a, int b){
return h[a] < h[b];
}
void build(int node=1, int tl=0, int tr=n-1){
if (tl == tr){
st[node] = {tl};
return;
}
int tm = (tl+tr)/2;
build(node*2, tl, tm);
build(node*2+1, tm+1, tr);
st[node] = st[node*2];
for (int x : st[node*2+1]) st[node].push_back(x);
sort(st[node].begin(), st[node].end(), comp);
/*cout << node << " " << tl << " " << tr << endl;
for (int x : st[node]) cout << x << " ";
cout << endl;*/
}
vector<int> query(int l, int r, int y, int node=1, int tl=0, int tr=n-1){
if (l <= tl && tr <= r){
vector<int> res;
int lo = -1, hi = st[node].size();
while (lo < hi-1){
int mid = (lo+hi)/2;
if (h[st[node][mid]] >= y) hi = mid;
else lo = mid;
}
for (int i=hi; i<(int)st[node].size(); i++) res.push_back(st[node][i]);
return res;
}
int tm = (tl+tr)/2;
vector<int> res;
if (l <= tm) res = query(l, r, y, node*2, tl, tm);
if (tm+1 <= r){
vector<int> v = query(l, r, y, node*2+1, tm+1, tr);
for (int x : v) res.push_back(x);
}
return res;
}
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();
int m = l.size();
::h = h;
st.resize(4*n);
build();
unordered_map<ll,vector<pair<ll,ll>>> um;
vector<vector<int>> bh(n);
bh[s].push_back(0);
bh[g].push_back(0);
for (int i=0; i<m; i++){
vector<int> val = query(l[i], r[i], y[i]);
sort(val.begin(), val.end());
/*cout << i << endl;
for (int x : val) cout << x << " ";
cout << endl;*/
for (int j=0; j<(int)val.size(); j++){
bh[val[j]].push_back(y[i]);
if (j+1 != (int)val.size()){
um[((ll)val[j]<<30)+y[i]].push_back({((ll)val[j+1]<<30)+y[i], x[val[j+1]]-x[val[j]]});
um[((ll)val[j+1]<<30)+y[i]].push_back({((ll)val[j]<<30)+y[i], x[val[j+1]]-x[val[j]]});
}
}
}
for (int i=0; i<n; i++){
sort(bh[i].begin(), bh[i].end());
/*cout << i << endl;
for (int x : bh[i]) cout << x << " ";
cout << endl;*/
for (int j=0; j+1<(int)bh[i].size(); j++){
um[((ll)i<<30)+bh[i][j]].push_back({((ll)i<<30)+bh[i][j+1], bh[i][j+1]-bh[i][j]});
um[((ll)i<<30)+bh[i][j+1]].push_back({((ll)i<<30)+bh[i][j], bh[i][j+1]-bh[i][j]});
}
}
priority_queue<pair<ll,ll>> pq;
pq.push({0, (ll)s<<30});
unordered_set<ll> seen;
while (!pq.empty()){
ll cur = pq.top().second, d = -pq.top().first;
pq.pop();
if (seen.find(cur) != seen.end()) continue;
//cout << (cur>>30) << " " << cur%(1ll<<30) << " " << d << endl;
seen.insert(cur);
if (cur == (ll)g<<30) return d;
for (pair<ll,ll> next : um[cur]) pq.push({-(d+next.second), next.first});
}
return -1;
}
