#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct segment{
int pos,ma;
segment(){
pos=ma=0;
}
segment(int a,int b){
pos=a;
ma=b;
}
};
segment merge(segment a,segment b){
segment ans;
if(a.ma>b.ma){
ans=a;
}else{
ans=b;
}
return ans;
}
int N;
vector<int> H,X;
vector<segment> seg;
void build(int id,int l,int r){
if(l==r){
seg[id]=segment(l,H[l]);
return;
}
int m=(l+r)/2;
build(id*2,l,m);
build(id*2+1,m+1,r);
seg[id]=merge(seg[id*2],seg[id*2+1]);
}
segment query(int id,int l,int r,int L,int R){
if(l>R||r<L){
return segment();
}else if(l>=L&&r<=R){
return seg[id];
}
int m=(l+r)/2;
return merge(query(id*2,l,m,L,R),query(id*2+1,m+1,r,L,R));
}
int cnt;
map<pair<int,int>,int> tran;
vector<set<int>> nodes;
vector<vector<pair<int,int>>> edges;
priority_queue<pair<int,int>> pq;
vector<int> dist;
void add(int l,int r,int y){
if(l+1>r-1){
if(!tran.count({X[l],y})){
tran[{X[l],y}]=cnt++;
nodes[l].insert(y);
}
if(!tran.count({X[r],y})){
tran[{X[r],y}]=cnt++;
nodes[r].insert(y);
}
edges[tran[{X[r],y}]].push_back({tran[{X[l],y}],X[r]-X[l]});
edges[tran[{X[l],y}]].push_back({tran[{X[r],y}],X[r]-X[l]});
return;
}
segment tmp=query(1,0,N-1,l+1,r-1);
if(tmp.ma>=y){
add(l,tmp.pos,y);
add(tmp.pos,r,y);
}else{
if(!tran.count({X[l],y})){
tran[{X[l],y}]=cnt++;
nodes[l].insert(y);
}
if(!tran.count({X[r],y})){
tran[{X[r],y}]=cnt++;
nodes[r].insert(y);
}
edges[tran[{X[r],y}]].push_back({tran[{X[l],y}],X[r]-X[l]});
edges[tran[{X[l],y}]].push_back({tran[{X[r],y}],X[r]-X[l]});
}
}
long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g) {
N=x.size();
int m=l.size();
H.resize(N);seg.resize(4*N);X.resize(N);edges.resize(N*m);nodes.resize(N);
for(int i=0;i<N;i++){
H[i]=h[i];
X[i]=x[i];
}
build(1,0,N-1);
for(int i=0;i<m;i++){
add(l[i],r[i],y[i]);
}
tran[{x[s],0}]=cnt++;tran[{x[g],0}]=cnt++;
nodes[s].insert(0);nodes[g].insert(0);
for(int i=0;i<N;i++){
int last=-1;
for(auto j:nodes[i]){
if(last!=-1){
edges[tran[{x[i],last}]].push_back({tran[{x[i],j}],j-last});
edges[tran[{x[i],j}]].push_back({tran[{x[i],last}],j-last});
}
last=j;
}
}
dist.resize(cnt,1e18);
pq.push({0,tran[{x[s],0}]});
dist[tran[{x[s],0}]]=0;
while(!pq.empty()){
int u=pq.top().second,t=-pq.top().first;
pq.pop();
if(dist[u]!=t){
continue;
}
for(int i=0;i<edges[u].size();i++){
int v=edges[u][i].first;
if(dist[v]>t+edges[u][i].second){
dist[v]=t+edges[u][i].second;
pq.push({-dist[v],v});
}
}
}
if(dist[tran[{x[g],0}]]==1e18){
return -1;
}
return dist[tran[{x[g],0}]];
}
