#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ALL(x) x.begin(),x.end()
#define SZ(x) x.size()
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ",_do(__VA_ARGS__)
template<typename T> void _do(T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT
const int maxn = 1e6;
struct Br{
int l,r,y;
};
struct Bd{
int x, y;
};
#define pli pair<ll, int>
#define pii pair<int, int>
#define f first
#define s second
vector<pii> g[maxn*2];
ll min_distance(vector<signed> x, vector<signed> h, vector<signed> il, vector<signed> ir, vector<signed> iy, signed startx, signed endx) {
int n = SZ(x), m = SZ(il);
vector<pii> in, out;
for (int i = 0; i<m; ++i) {
in.pb({il[i], iy[i]});
out.pb({ir[i], iy[i]});
}
in.pb({0,0});
out.pb({0,0});
in.pb({n-1,0});
out.pb({n-1,0});
sort(ALL(in), [&](pii a, pii b){return a.f!=b.f?a.f<b.f:a.s>b.s;});
sort(ALL(out), [&](pii a, pii b){return a.f!=b.f?a.f<b.f:a.s>b.s;});
m+=2;
// sort(ALL(bds), [&](Bd a, Bd b) { return a.y > b.y; });
map<int, int> cut;
vector<map<int, int> > hv(n);
int ID = 0;
int oj = 0, ij = 0;
int S, T;
// set<int> dontkill;
map<int, int> ans; // answer for this
for (int i = 0; i<n; ++i) {
// set<int> app; // newly appeared
while (ij < m && in[ij].f <= i) {
int H = in[ij].s;
if (cut[H]==0) {
// app.insert(H);
if (i == 0) {
ans[H] = H;
}else{
ans[H] = 0x3f3f3f3f3f3f3f3f;
auto iter = ans.upper_bound(H);
if (iter!=ans.end()) {
ans[H] = iter->s + abs((iter-> f)- H);
}
if (iter!=ans.begin()) {
--iter;
ans[H] = min(ans[H], iter->s + abs((iter-> f)- H));
}
}
bug(H, ans[H]);
}else{
bug(H, cut[H]);
}
++cut[(H)];
++ij;
if (H == 0 && i==n-1) {
bug(H, ans[H]);
if (ans[H] == 0x3f3f3f3f3f3f3f3f) return -1;
return ans[H] + x[n-1] - x[0];
}
}
//// bug(i, SZ(cut));
// int prvid = ID++, prvh = 0;
// if (i == startx) S = prvid;
// if (i == endx) T = prvid;
while (oj < m && out[oj].f <= i) {
--cut[out[oj].s];
bug("minus",out[oj].s);
if (cut[out[oj].s] == 0) {
cut.erase(out[oj].s);
ans.erase(out[oj].s);
}
++oj;
}
}
// bug(ID, S, T);
// vector<ll> d(ID, 0x3f3f3f3f3f3f3f3f);
// priority_queue<pli, vector<pli >, greater<pli> > pq;
// d[S] = 0;
// pq.push({0,S});
// while (!pq.empty()) {
// ll w = pq.top().f;
// int v = pq.top().s;
// pq.pop();
// if (d[v] != w) continue;
// for (pii u : g[v]) {
// if (d[u.f] > w + u.s) {
// d[u.f] = w + u.s;
// pq.push({d[u.f], u.f});
// }
// }
// }
// for (int i = 0; i<ID; i++) {
// for (pii u : g[i]) {
// bug(i,u.f, u.s);
// }
// }
// for (int i = 0; i<ID; i++) {
// bug(i, d[i]);
// }
// if (d[T] == 0x3f3f3f3f3f3f3f3f) d[T] = -1;
return -1;
}
#ifdef BALBIT
signed main(){
IOS();
// int MO = min_distance({0, 4, 5, 6, 9},
//{6, 6, 6, 6, 6},
//{3, 1, 0},
//{4, 3, 2},
//{1, 3, 6},
//0, 4);
// bug(MO);
int MO2 = min_distance({0, 3, 5, 7, 10, 12, 14},
{8, 7, 9, 7, 6, 6, 9},
{0, 0, 0, 2, 2, 3, 4, 5},
{1, 2, 6, 3, 6, 4, 5, 6},
{1, 6, 8, 1, 7, 2, 5, 5},
0, 6);
bug(MO2);
}
#endif
