#include <bits/stdc++.h>
#include "walk.h"
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=1e5+1;
const ll inf=1e18;
map<int,ll> dp[N];
int y[N];
struct setik{
map<pii,ll> dp;
void upd(pii i,ll x){
dp[i]=x;
auto it=dp.lower_bound(i);
if(it!=dp.begin() && prev(it)->s>dp[i])
upd(prev(it)->f,x);
}
void getval(pii i,int yt){
// cout<<"W "<<i.f<<' '<<i.s<<endl;
dp[i]=inf;
auto it=dp.lower_bound(i);
ll vl=inf;
if(next(it)!=dp.end() && y[next(it)->f.s]<=yt)
umin(vl,next(it)->s);
if(it!=dp.begin()){
// cout<<prev(it)->f.s<<' '<<i.
umin(vl,2*abs(y[prev(it)->f.s]-y[i.s])+prev(it)->s);
}
upd(i,vl);
}
}_dp;
vec<pii> scan[N];
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){
set<int> st;
int n=sz(x);
int m=sz(l);
{
vec<int> p(m);
for(int i=0;i<m;i++) p[i]=i;
sort(all(p),[&](int i,int j){return y[i]<y[j];});
vec<int> nl(m),nr(m),ny(m);
for(int i=0;i<m;i++)
nl[i]=l[p[i]],nr[i]=r[p[i]],ny[i]=y[p[i]];
swap(l,nl);swap(r,nr);swap(y,ny);
// for(auto &z : y)
// cout<<z<<' ';
// cout<<endl;
}
// y.pb(0);
// l.pb(n),r.pb(-1);
{
vec<array<int,3>> haha;
st.insert(-1);
st.insert(n);
for(int i=0;i<n;i++) haha.pb({h[i],1,i});
for(int i=0;i<m;i++) haha.pb({y[i],0,i});
sort(rall(haha));
for(auto &z : haha){
if(z[1]==0){
l[z[2]]=*st.lower_bound(l[z[2]]);
r[z[2]]=*prev(st.upper_bound(r[z[2]]));
}
else{
st.insert(z[2]);
}
}
st.clear();
}
for(int i=0;i<m;i++){
if(l[i]>r[i]) continue;
scan[l[i]].pb({i,1});
scan[r[i]+1].pb({i,-1});
::y[i]=y[i];
}
if(s==0 && g==n-1){
for(auto &z : scan[0]){
_dp.upd(m_p(y[z.f],z.f),2*y[z.f]);
}
for(int i=1;i<n;i++){
for(auto &z : scan[i]){
if(z.s==-1){
// cout<<"DEL "<<z.f<endl;
_dp.dp.erase(m_p(y[z.f],z.f));
}
}
auto it=_dp.dp.upper_bound(m_p(h[i-1],1e9));
if(it!=_dp.dp.end() && it->f.f<=h[i]){
auto itj=_dp.dp.upper_bound(m_p(h[i],-1));
--itj;
if(itj->s!=inf){
while(it->s==inf) ++it;
_dp.upd(it->f,it->s);
}
}
for(auto &z : scan[i]){
if(z.s==-1) continue;
_dp.getval(m_p(y[z.f],z.f),h[i]);
}
// cout<<i<<endl;
// for(auto &q : _dp.dp)
// cout<<q.f<<' '<<q.s<<endl;
// cout<<endl;
}
ll mn=inf;
for(auto &z : _dp.dp)
umin(mn,z.s+x[n-1]-x[0]);
if(mn==inf)
mn=-1;
return mn;
}
vec<vec<int>> ids(m,vec<int>());
for(int i=0;i<n;i++){
dp[i][-1]=inf;
for(auto &z : scan[i]){
if(z.s==-1)
st.erase(z.f);
else
st.insert(z.f);
}
for(auto z : st){
if(y[z]>h[i]) break;
// cout<<"I "<<i<<' '<<z<<endl;
dp[i][z]=inf;
ids[z].pb(i);
}
}
priority_queue<array<ll,3>,vec<array<ll,3>>,greater<array<ll,3>>> pq;
pq.push({0,s,-1});
dp[s][-1]=0;
while(!pq.empty()){
auto [xt,v,j]=pq.top();pq.pop();
if(dp[v][j]!=xt) continue;
// cout<<v<<' '<<j<<' '<<dp[v][j]<<endl;
auto getnxt=[&](int v,int j){
if(j==-1)
return n;
int w=lower_bound(all(ids[j]),v)-ids[j].begin();
if(w==sz(ids[j])-1)
return n;
return ids[j][w+1];
};
auto getprv=[&](int v,int j){
if(j==-1)
return -1;
int w=lower_bound(all(ids[j]),v)-ids[j].begin();
if(w==0)
return -1;
return ids[j][w-1];
};
int f=getnxt(v,j),s=getprv(v,j);
for(auto &z : {f,s}){
if(z==n || z==-1)
continue;
if(umin(dp[z][j],xt+abs(x[z]-x[v])))
pq.push({dp[z][j],z,j});
}
// assert(dp[v].count(j));
auto it=dp[v].find(j);
// cout<<next(it)->f<<endl;
if(next(it)!=dp[v].end()){
int nj=next(it)->f;
int r=abs((nj==-1?0:y[nj])-(j==-1?0:y[j]));
if(umin(dp[v][nj],xt+r))
pq.push({dp[v][nj],v,nj});
}
if(it!=dp[v].begin()){
int nj=prev(it)->f;
int r=abs((nj==-1?0:y[nj])-(j==-1?0:y[j]));
if(umin(dp[v][nj],xt+r))
pq.push({dp[v][nj],v,nj});
}
}
if(dp[g][-1]==inf)
dp[g][-1]=-1;
return dp[g][-1];
}
