#include "walk.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 1e5 + 10;
const long long inf = 1e18;
int n , m , a[N] , pos[N];
vector <int> all[N];
vector <long long> dis[N];
vector <bool> marked[N];
vector <vector<pair<pair<int , int> , int>>> adj[N];
struct bridge{
int l , r , y;
};
vector <bridge> vec;
bool cmp(bridge aa , bridge bb)
{
return aa.y < bb.y;
}
struct SEG{
int mx[N << 2];
void Build(int node = 1 , int nl = 0 , int nr = n)
{
if(nr - nl == 1)
{
mx[node] = a[nl];
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Build(lc , nl , mid); Build(rc , mid , nr);
mx[node] = max(mx[lc] , mx[rc]);
}
int Get(int id , int val , int node = 1 , int nl = 0 , int nr = n)
{
if(nr <= id || mx[node] < val)
return -1;
if(nr - nl == 1)
return nl;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
int tmp = Get(id , val , lc , nl , mid);
if(tmp == -1)
return tmp = Get(id , val , rc , mid , nr);
return tmp;
}
} seg;
void Add(int l , int r , int y)
{
int now = l;
all[now].push_back(y);
adj[now].emplace_back();
while(now != r)
{
int id = seg.Get(now + 1 , y);
all[id].push_back(y);
adj[id].emplace_back();
adj[now].back().push_back(make_pair(make_pair(id , all[id].size() - 1) , pos[id] - pos[now]));
adj[id].back().push_back(make_pair(make_pair(now , all[now].size() - 1) , pos[id] - pos[now]));
now = id;
}
}
void Dij()
{
priority_queue <pair<long long , pair<int , int>>> pq;
for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < all[i].size() ; j++)
pq.push(make_pair(-dis[i][j] , make_pair(i , j)));
while(!pq.empty())
{
auto now = pq.top();
pq.pop();
long long D = abs(now.F);
int x = now.S.F , y = now.S.S;
if(marked[x][y])
continue;
//cout << x << " " << y << " :::: " << D << endl;
marked[x][y] = true;
for(auto u : adj[x][y]) if(dis[u.F.F][u.F.S] > D + u.S)
{
dis[u.F.F][u.F.S] = D + u.S;
pq.push(make_pair(-dis[u.F.F][u.F.S] , u.F));
}
}
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
n = x.size();
m = l.size();
for(int i = 0 ; i < n ; i++)
{
a[i] = h[i];
pos[i] = x[i];
}
for(int i = 0 ; i < m ; i++)
{
vec.push_back({l[i] , r[i] , y[i]});
}
sort(vec.begin() , vec.end() , cmp);
seg.Build();
for(auto u : vec)
{
Add(u.l , u.r , u.y);
}
for(int i = 0 ; i < n ; i++) for(int j = 0 ; j + 1 < all[i].size() ; j++)
{
adj[i][j].push_back(make_pair(make_pair(i , j + 1) , all[i][j + 1] - all[i][j]));
adj[i][j + 1].push_back(make_pair(make_pair(i , j) , all[i][j + 1] - all[i][j]));
}
/*for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < all[i].size() ; j++)
{
cout << i << " " << j << " : " << all[i][j] << endl;
for(auto u : adj[i][j])
cout << u.F.F << " " << u.F.S << " " << u.S << endl;
}*/
for(int i = 0 ; i < n ; i++)
{
dis[i].resize(all[i].size() , inf);
marked[i].resize(all[i].size());
}
for(int i = 0 ; i < all[s].size() ; i++)
dis[s][i] = all[s][i];
Dij();
long long res = inf;
for(int i = 0 ; i < all[g].size() ; i++)
res = min(res , dis[g][i] + all[g][i]);
if(res == inf)
res = -1;
return res;
}
