#include "walk.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i =k; i<n; i++)
#define vi vector<int>
#define pii pair<int,int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define vpii vector<pii>
#define mii map<int,int>
#define dout(x) cout<<x<<' '<<#x<<endl;
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<endl;
#define out(x) cout<<x<<endl;
#define out2(x,y) cout<<x<<' '<<y<<endl;
using namespace std;
const int mxn = (1e5 * 13);
vector<vi>adj(mxn);
struct event{
int x, d, type;
};
bool cmp(event a, event b){
return b.x>a.x;
}
int min_distance(vector<signed> x, vector<signed> h, vector<signed> l, vector<signed> r, vector<signed> y, signed S, signed g) {
//encode a position as h * n + i
int n = x.size();
int m = l.size();
/*
vvi pts(m);
vector<pair<int,pair<pii,int>>>edges;
f0r(i,m){
edges.pb(mp(y[i], mp(mp(l[i], r[i]),i)));
}
sort(edges.rbegin(), edges.rend());
set<int>active;
vector<pair<int, pii>> nodes;
f0r(i,n){
nodes.pb(mp(h[i], mp(x[i], i)));
}
sort(nodes.rbegin(), nodes.rend());
int p1 = 0;
int p2 = 0;
vi nxt(n, -1);
while(p1 < m){
if(p2 == n){
auto it = lower_bound(active.begin(), active.end(), edges[p1].second.first.first);
int cur = *it;
int d = edges[p1].second.second;
while(cur != -1 && cur <= edges[p1].second.first.second){
pts[d].pb(cur);
cur = nxt[cur];
}
p1++;
}
else{
if(edges[p1].first > nodes[p2].first){
//compute edge
auto it = lower_bound(active.begin(), active.end(), edges[p1].second.first.first);
int cur = *it;
int d = edges[p1].second.second;
while(cur != -1 && cur <= edges[p1].second.first.second){
pts[d].pb(cur);
cur = nxt[cur];
}
p1++;
}
else{
auto it = lower_bound(active.begin(), active.end(), nodes[p2].second.second);
if(it != active.end())nxt[nodes[p2].second.second] = *it;
if(it != active.begin()){
--it;
nxt[*it] = nodes[p2].second.second;
}
active.insert(nodes[p2].second.second);
p2++;
}
}
}
f0r(i,m){
sort(pts[i].begin(), pts[i].end());
}
vector<vpii> ints(n);
int cnt = n;
f0r(i,m){
for(int k = 0; k<pts[i].size(); k++){
int j = pts[i][k];
ints[j].pb(mp(y[i], cnt));
cnt++;
if(k > 0){
int j = pts[i][k-1];
int j2 = pts[i][k];
adj[cnt-1].pb(mp(cnt-2, x[j2] - x[j]));
adj[cnt-2].pb(mp(cnt-1, x[j2] - x[j]));
}
}
}
f0r(i,n){
ints[i].pb(mp(0, i));
}
f0r(i,n){
sort(ints[i].begin(), ints[i].end());
}
f0r(i,n){
f0r(j, ints[i].size() - 1){
int h1 = ints[i][j].first;
int h2 = ints[i][j+1].first;
adj[ints[i][j].second].pb(mp(ints[i][j+1].second, h2-h1));
adj[ints[i][j+1].second].pb(mp(ints[i][j].second, h2-h1));
}
}
vi dist(mxn, 4e18);
dist[s] = 0;
priority_queue<pii>q;
q.push(mp(0,s));
while(!q.empty()){
int node = q.top().second;
q.pop();
for(auto u : adj[node]){
int b = u.first;
int w = u.second;
if(dist[b] > dist[node] + w){
dist[b] = dist[node] + w;
q.push(mp(-dist[b], b));
}
}
}
*/
/*
out(dist[n + 1]);
out(dist[6 * n + 1]);
out(dist[6 * n + 2]);
out(dist[7*n+2]);
out(dist[7*n+6]);
out(dist[5*n+6]);
out(dist[5*n+5]);
*/
vector<event>events;
f0r(i, m){
events.pb({l[i], i, 0});
events.pb({r[i], i, 1});
}
sort(events.begin(), events.end(), cmp);
/*
for(auto u : events){
cout<<u.x<<'\n';
}
*/
set<pii>s;
f0r(i, events.size()){
if(events[i].type == 0){
s.insert(mp(y[events[i].d], events[i].d));
}
else{
auto it = lower_bound(s.begin(), s.end(), mp((int)y[events[i].d], -1LL));
if(events[i].d == 2){
// dout(y[events[i].d]);
// dout(s.size());
}
if(it != s.end())adj[events[i].d].pb((*it).second);
if(it != s.begin()){
it--;
adj[events[i].d].pb((*it).second);
}
}
}
/*
f0r(i,m){
vout(adj[i]);
}
*/
// vout(adj[mxn-2]);
vi dist(mxn, 4e18);
dist[mxn-2] = 0;
priority_queue<pii>q;
f0r(i, m){
if(l[i] == 0){
adj[mxn-2].pb(i);
}
if(r[i] == n-1){
adj[i].pb(mxn-1);
}
}
q.push(mp(0,mxn-2));
while(!q.empty()){
int node = q.top().second;
// dout(node);
q.pop();
for(auto u : adj[node]){
int b = u;
int w;
if(node == mxn-2){
w = y[b];
}
else if(b == mxn - 1){
w = y[node];
}
else{
w = abs(y[node] - y[b]);
}
if(dist[b] > dist[node] + w){
dist[b] = dist[node] + w;
q.push(mp(-dist[b], b));
}
}
}
if(dist[mxn-1] == 4e18)return -1;
else return dist[mxn-1] + x[n-1] - x[0];
return 1;
}
