#include "bits/stdc++.h"
#include "walk.h"
using namespace std;
const int maxNode = 2e6 + 10;
const int maxn = 1e5 + 10;
const long long inf = 1e16;
int node = 0;
vector <pair <int, int>> g[maxNode];
vector <int> start[maxn], fin[maxn];
vector <pair <int, int>> bridge[maxn];
struct vertex {
int node;
long long dist;
vertex() {}
vertex(int node, long long dist) : node(node), dist(dist) {}
bool operator < (vertex v) const {
return dist > v.dist;
}
};
void addEdge(int i, int j, int cost) {
g[i].emplace_back(j, cost);
g[j].emplace_back(i, cost);
}
long long shortest_path(int src, int des) {
priority_queue <vertex> Q;
vector <long long> dist (node, inf);
Q.emplace(src, 0);
dist[src] = 0;
while(not Q.empty()) {
auto x = Q.top();
Q.pop();
if(x.dist != dist[x.node]) continue;
for(auto i : g[x.node]) {
if(i.second + x.dist < dist[i.first]) {
dist[i.first] = i.second + x.dist;
Q.emplace(i.first, dist[i.first]);
}
}
}
return dist[des];
}
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 from, int to) {
for(int i = 0; i < l.size(); i++) {
start[l[i]].push_back(i);
fin[r[i]].push_back(i);
}
set <pair <int, int>> cont;
int src = 0, des = 0;
for(int i = 0; i < x.size(); i++) {
for(int j : start[i]) {
cont.insert(make_pair(y[j], j));
}
vector <pair <int, int>> can;
if(from == i) {
can.push_back(make_pair(0, -1));
src = node;
}
if(to == i) {
can.push_back(make_pair(0, -1));
des = node;
}
for(int j : start[i]) {
auto it = cont.find(make_pair(y[j], j));
can.emplace_back(y[j], j);
if(it != cont.begin()) {
can.push_back(*prev(it));
}
if(next(it) != cont.end() && next(it) -> first <= h[i]) {
can.push_back(*next(it));
}
}
for(int j : fin[i]) {
auto it = cont.find(make_pair(y[j], j));
can.emplace_back(y[j], j);
if(it != cont.begin()) {
can.push_back(*prev(it));
}
if(next(it) != cont.end() && next(it) -> first <= h[i]) {
can.push_back(*next(it));
}
}
sort(can.begin(), can.end());
for(int j = 0; j < can.size(); j++) {
if(can[j].second == -1) continue;
bridge[can[j].second].emplace_back(x[i], node + j);
}
for(int j = 1; j < can.size(); j++) {
addEdge(node + j - 1, node + j, can[j].first - can[j - 1].first);
}
node += can.size();
for(int j : fin[i]) {
cont.erase(make_pair(y[j], j));
}
}
for(int i = 0; i < l.size(); i++) {
sort(bridge[i].begin(), bridge[i].end());
for(int j = 1; j < bridge[i].size(); j++) {
addEdge(bridge[i][j - 1].second, bridge[i][j].second,
bridge[i][j].first - bridge[i][j - 1].first);
}
}
auto ans = shortest_path(src, des);
return ans >= inf ? -1 : ans;
}
