#include <bits/stdc++.h>
#include "walk.h"
#define sz(x) (int)x.size()
#define mkt make_tuple
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define debug printf
#define all(x) x.begin(),x.end()
#define tiii tuple<int,int,int>
const int MAXN = 1e5+100 ;
const int inf = 1e9+7 ;
const ll linf = 1e18+10 ;
using namespace std ;
struct Seg
{
vector<int> y ;
int id[MAXN*4] , mx[MAXN*4] ;
int m(int l, int r) { return (l+r)>>1 ; }
void upd(int pos, int l, int r, int beg, int en , int k )
{
if( l > en || r < beg ) return ;
mx[pos] = k ;
if(l >= beg && r <= en)
{
id[pos] = k ;
return ;
}
upd(pos<<1 , l, m(l,r) , beg, en, k ) ;
upd(pos<<1|1 , m(l,r) + 1 , r , beg, en ,k ) ;
}
int qry(int pos, int l, int r, int beg, int en)
{
if( l > en || r < beg ) return sz(y)-1 ;
if( l >= beg && r <= en ) return mx[pos] ;
int al = qry(pos<<1 , l, m(l,r) , beg, en ) ;
int ar = qry(pos<<1|1 , m(l,r)+1, r, beg, en ) ;
if( y[ id[pos] ] <= min( y[ al ] , y[ar] ) ) return id[pos] ;
return y[al] < y[ar] ? al : ar ;
}
} seg ;
struct Event
{
int y , l , r , id ;
Event(int y = 0 ,int l = 0 , int r = 0 , int id = 0 ) : y(y) , l(l) , r(r) , id(id) {}
bool operator < ( Event other ) const { return y > other.y ; }
};
int N , M , S , G ;
vector<Event> sweep ;
vector<pii> adj[MAXN] ;
ll dist[MAXN] ;
void dijkstra()
{
lp(i,0,M) dist[i] = linf ;
dist[M-2] = 0 ;
priority_queue< pair<ll,int> , vector<pair<ll,int> > , greater< pair<ll,int> > > fila ;
fila.push(mk(0,M-2)) ;
while(!fila.empty())
{
int x = fila.top().ss ;
ll d = fila.top().ff ;
fila.pop() ;
if(d != dist[x]) continue ;
for(auto e : adj[x] )
{
ll dd = d + (ll)e.ss ;
if(dd >= dist[e.ff]) continue ;
fila.push( mk( (dist[e.ff] = dd) , e.ff ) ) ;
}
}
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
if(s == g) return 0LL ;
N = sz(x) ;
l.pb(0) ;
r.pb(0) ;
y.pb(0) ;
l.pb( N-1 ) ;
r.pb(N-1) ;
y.pb(0) ;
M = sz(l) ;
S = s ;
G = g ;
lp(i,0,M)
{
sweep.pb( Event( y[i] , l[i] , r[i] , i) ) ;
seg.y.pb( y[i] ) ;
}
seg.y.pb( inf ) ;
lp(i,0,MAXN*4) seg.id[i] = seg.mx[i]= sz(seg.y) - 1 ;
sort(all(sweep)) ;
for(auto e : sweep )
{
// debug("Processing %d %d %d\n" , e.y , e.l , e.r ) ;
int mnY = seg.qry( 1 , 1 , N , e.l + 1 , e.r+1 ) ;
seg.upd(1,1,N, e.l + 1 ,e.r + 1 , e.id ) ;
//debug("E deu %d\n\n" , mnY ) ;
if( mnY == sz(y) ) continue ;
adj[ mnY ].pb( mk( e.id , y[mnY] - y[e.id] ) ) ;
adj[e.id].pb( mk( mnY , y[mnY] - y[e.id] ) ) ;
}
/* lp(i,0,M)
{
debug("Adjacency of %d (%d %d %d):\n", i , l[i] , r[i] , y[i] ) ;
for(auto e : adj[i]) debug("%d %d\n" , e.ff, e.ss ) ;
debug("\n") ;
} */
dijkstra() ;
if( dist[M-1] == linf ) return -1 ;
return x[N-1] - x[0] + dist[M-1] ;
}
