#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;
void change(vi&l,vi &r,vi&y,vi&x,vi&h,int s)
{
int n=x.size(),q=l.size();
vector<pi> cur;
for(int i=0;i<n;i++)
{
cur.push_back({x[i],i});
}
for(int i=0;i<q;i++)
{
cur.push_back({y[i],-i-1});
}
set<int> have;
sort(begin(cur),end(cur));
reverse(begin(cur),end(cur));
vi lp,rp,yp;
for(int id=0;id<n+q;id++)
{
int i=cur[id].second;
if(i>=0)
{
// building
have.insert(i);
}
else
{
i=-i-1;
if(l[i]<s and s<r[i])
{
int a=-1,b=-1;
auto it=have.lower_bound(s);
if(it!=have.end() and (*it)<=r[i])
b=*it;
it=have.upper_bound(s);
if(it!=begin(have))
{
it--;
a=*it;
}
if(b==-1)b=r[i];
if(a==-1)a=b;
lp.push_back(l[i]);
rp.push_back(a);
yp.push_back(y[i]);
lp.push_back(a);
rp.push_back(b);
yp.push_back(y[i]);
lp.push_back(b);
rp.push_back(r[i]);
yp.push_back(y[i]);
}
else
{
lp.push_back(l[i]);
rp.push_back(r[i]);
yp.push_back(y[i]);
}
// l[i] r[i]
}
}
// add maximum first
l=lp;
r=rp;
y=yp;
}
int n,q;
const int M=2e5+10,N=4e6+10;
set<int> pts[M];
vector<int> add[M],del[M];
const ll inp=1e18;
ll dp[N];
const int inf=2e9;
vector<pair<ll,int>> ma[N];
map<int,int> mp[M];
int lstp=0;
int get(int x,int y)
{
if(mp[x].find(y)==mp[x].end())
{
mp[x][y]=lstp++;
}
return mp[x][y];
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
l.push_back(s);
l.push_back(g);
r.push_back(s);
r.push_back(g);
y.push_back(0);
y.push_back(0);
change(l,r,y,x,h,s);
change(l,r,y,x,h,g);
q=l.size();
n=x.size();
for(int i=0;i<q;i++)
{
add[l[i]].push_back(i);
del[r[i]].push_back(i);
pts[i].insert(l[i]);
pts[i].insert(r[i]);
// insert(l[i],r[i],y[i],i);
}
set<pair<int,int>> sky;
for(int i=0;i<n;i++)
{
for(auto j:add[i])
sky.insert({y[j],j});
for(auto j:add[i])
{
auto it=sky.upper_bound({y[j],-1});
if(it!=end(sky) and it->first<=h[i])
{
bool pl=0;
if(it->second==j)
{
it++;
pl=1;
}
if(it!=end(sky) and it->first<=h[i])
{
int k=it->second;
int cx=get(i,y[k]);
int nx=get(i,y[j]);
ll d=abs(y[k]-y[j]);
pts[j].insert(i);
pts[k].insert(i);
}
if(pl)
{
it--;
}
}
if(it!=begin(sky))
{
it--;
int k=it->second;
int cx=get(i,y[k]);
int nx=get(i,y[j]);
ll d=abs(y[k]-y[j]);
pts[j].insert(i);
pts[k].insert(i);
}
}
for(auto j:del[i])
{
auto it=sky.upper_bound({y[j],-1});
if(it!=end(sky) and it->first<=h[i])
{
bool pl=0;
if(it->second==j)
{
it++;
pl=1;
}
if(it!=end(sky) and it->first<=h[i])
{
int k=it->second;
int cx=get(i,y[k]);
int nx=get(i,y[j]);
ll d=abs(y[k]-y[j]);
pts[j].insert(i);
pts[k].insert(i);
}
if(pl)
{
it--;
}
}
if(it!=begin(sky))
{
it--;
int k=it->second;
int cx=get(i,y[k]);
int nx=get(i,y[j]);
ll d=abs(y[k]-y[j]);
pts[j].insert(i);
pts[k].insert(i);
}
}
for(auto j:del[i])
sky.erase({y[j],j});
}
for(int i=0;i<n;i++)
{
// for(auto [y,id]:mp[i])
// {
// cout<<"for inter at "<<i<<" height "<<y<<" id is "<<id<<endl;
// }
vector<pair<int,int>> cur(begin(mp[i]),end(mp[i]));
for(int j=1;j<cur.size();j++)
{
int cx=cur[j-1].second;
int nx=cur[j].second;
int d=cur[j].first-cur[j-1].first;
ma[cx].push_back({d,nx});
ma[nx].push_back({d,cx});
}
}
for(int i=0;i<q;i++)
{
vector<int> cul(begin(pts[i]),end(pts[i]));
for(int j=1;j<cul.size();j++)
{
int cx=get(cul[j],y[i]);
int nx=get(cul[j-1],y[i]);
ll d=abs(x[cul[j]]-x[cul[j-1]]);
ma[cx].push_back({d,nx});
ma[nx].push_back({d,cx});
}
}
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
for(int i=0;i<N;i++)dp[i]=inp;
dp[get(s,0)]=0;
pq.push({0,get(s,0)});
while(pq.size())
{
auto [mn,x]=pq.top();
pq.pop();
if(dp[x]!=mn)continue;
// cout<<"PQ "<<x<<' '<<dp[x]<<endl;
for(auto [w,y]:ma[x])
{
// cout<<w<<' '<<y<<' '<<x<<endl;
if(dp[y]>dp[x]+w)
{
// cout<<"updating "<<y<<" from "<<x<<' '<<w<<endl;
dp[y]=dp[x]+w;
pq.push({dp[y],y});
}
}
}
if(dp[get(g,0)]==inp)return -1;
return dp[get(g,0)];
}
