#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
const int base = 1<<17;
int tree[2*base];
void ustaw(int w, int l, int p, int a, int b, int v){
if(a<=l && p<=b){
tree[w] = v;
return;
}
if(b<l || p<a)return;
if(tree[w]!=-1)
tree[w*2] = tree[w*2+1] = tree[w];
ustaw(w*2, l, (l+p)/2, a, b, v);
ustaw(w*2+1, (l+p)/2+1, p, a, b, v);
tree[w] = -1;
}
int odczyt(int w){
int res = -1;
w+=base;
while(w>0){
if(tree[w]!=-1)
res = tree[w];
w/=2;
}
return res;
}
vector<int>l,r,y;
void dodaj(int a, int b, int h){
l.push_back(a);
r.push_back(b);
y.push_back(h);
}
vector<pair<int,long long>>graf[700010];
long long dist[700010];
bool odw[700010];
long long min_distance(vector<int> x, vector<int> h, vector<int> L, vector<int> R, vector<int> Y, int s, int g) {
// podzielic kazda pozioma
// dla kazdej poziomej wyznaczyc pozioma w dol z obu koncy
vector<tuple<int,int,int,int>>przedzialy;
int n = x.size();
int m = L.size();
int i;
if(s>g)swap(s,g);
for(i=0;i<m;i++){
if(L[i]<s && R[i]>g){
// printf("%d 3\n", i);
dodaj(L[i],s,Y[i]);
dodaj(s,g,Y[i]);
dodaj(g,R[i],Y[i]);
}
else if(L[i]<s && R[i]>s){
// printf("%d 2\n", i);
dodaj(L[i],s,Y[i]);
dodaj(s,R[i],Y[i]);
}
else if(g<R[i] && L[i]<g){
// printf("%d 2\n", i);
dodaj(L[i],g,Y[i]);
dodaj(g,R[i],Y[i]);
}
else{
// printf("%d 1\n");
dodaj(L[i],R[i],Y[i]);
}
}
m = l.size();
//for(i=0;i<m;i++)printf("%d %d %d %d\n", y[i], l[i], r[i], i);printf("\n");
for(i=0;i<m;i++)
przedzialy.push_back({y[i],l[i],r[i],0});
sort(przedzialy.begin(), przedzialy.end());
for(i=0;i<m;i++)
get<3>(przedzialy[i]) = i;
for(i=0;i<n;i++)tree[i+base] = -1;
for(i=base-1;i>0;i--)
tree[i] = -1;
ustaw(1, 0,base-1,s,s,0);
ustaw(1, 0,base-1,g,g,1);
for(auto j: przedzialy){
auto [Y,L,R,i] = j;
int b;
for(int ij=0;ij<2;ij++){
int a = odczyt(ij?R:L);
int s = (a-2)/2;
b = i*2+2+ij;
// if(ij==0)printf("LEWY: %d %d(%d)\n", b, a,s);
// else printf("PRAWY: %d %d(%d)\n", b, a,s);
if(a==-1)continue;
if(a==0 || a==1){
graf[b].push_back({a,Y});
graf[a].push_back({b,Y});
}
else{
long long d;
d=Y-get<0>(przedzialy[s])+abs(x[ij?R:L]-x[get<1>(przedzialy[s])]);
graf[b].push_back({a, d});
graf[a].push_back({b, d});
d=Y-get<0>(przedzialy[s])+abs(x[ij?R:L]-x[get<2>(przedzialy[s])]);
graf[b].push_back({a^1, d});
graf[a^1].push_back({b, d});
}
}
graf[b].push_back({b-1, abs(x[L]-x[R])});
graf[b-1].push_back({b, abs(x[L]-x[R])});
ustaw(1, 0, base-1, L, R, b-1);
// printf("%d %d %d: %d %d\n", y[i], l[i], r[i], b-1, b);
}/*
for(i=0;i<(int)przedzialy.size()*2+2;i++){
printf("%d: ", i);
for(auto j: graf[i])
printf("%d-%d ", j.first, j.second);
printf("\n");
}*/
priority_queue<pair<long long, int>>kolejka;
dist[0] = 1;
kolejka.push({-1,0});
while(kolejka.size()){
auto a = kolejka.top();
kolejka.pop();
if(odw[a.second])continue;
odw[a.second]=1;
for(auto j: graf[a.second]){
if(dist[j.first]==0 || dist[j.first]>dist[a.second]+j.second){
dist[j.first]=dist[a.second]+j.second;
kolejka.push({-dist[j.first], j.first});
}
}
}
return dist[1]-1;
}
