#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<int,int>,int> > v;
vector<pair<int,long long> > adjl[100005];
long long dist[100005];
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) {
for (int x = 0; x<l.size(); x++){
v.push_back({{l[x],0},x});
v.push_back({{r[x],1},x});
}
sort(v.begin(),v.end());
set<pair<int,int> > S;
int stn = l.size();
int endn = l.size()+1;
for (auto x : v){
if (x.first.second==0){
auto it = S.lower_bound({y[x.second],x.second});
if (it!=S.end()){
adjl[x.second].push_back({(*it).second,abs(y[x.second]-y[(*it).second])});
adjl[(*it).second].push_back({x.second,abs(y[x.second]-y[(*it).second])});
//printf("add edge %d-%d, %d\n",x.second,(*it).second,abs(y[x.second]-y[(*it).second]));
}
if (it!=S.begin()){
it--;
adjl[x.second].push_back({(*it).second,abs(y[x.second]-y[(*it).second])});
adjl[(*it).second].push_back({x.second,abs(y[x.second]-y[(*it).second])});
//printf("Add edge %d-%d, %d\n",x.second,(*it).second,abs(y[x.second]-y[(*it).second]));
}
S.insert({y[x.second],x.second});
}
else{
auto it = S.lower_bound({y[x.second],x.second});
S.erase(it);
}
if (x.first.first==0 && x.first.second==0){
adjl[stn].push_back({x.second,y[x.second]});
}
if (x.first.first==(int)X.size()-1 && x.first.second==1){
adjl[x.second].push_back({endn,y[x.second]});
}
}
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > >pq;
memset(dist,-1,sizeof(dist));
dist[stn] = 0;
pq.push({0,stn});
while (!pq.empty()){
int nd = pq.top().second;
long long d = pq.top().first;
pq.pop();
if (d>dist[nd]) continue;
//printf("d[%d] = %d\n",nd,d);
for (auto x : adjl[nd]){
if (dist[x.first]==-1 || d+x.second<dist[x.first]){
dist[x.first] = d+x.second;
pq.push({dist[x.first],x.first});
}
}
}
assert(dist[endn]!=-1);
//printf("distThing = %d\n",dist[endn]);
return dist[endn] + (long long)*X.begin()+ (long long)(*--X.end());
}
