#include "walk.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <deque>
#include <queue>
#include <algorithm>
#include <string>
#include <cassert>
#include <memory>
#include <numeric>
#include <functional>
#include <random>
#define ll long long
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define length(a) ((int)a.size())
using namespace std;
template<class iterator> void output(iterator begin, iterator end, ostream &out = cerr) {
while (begin != end) {
out << (*begin) << " ";
begin++;
}
out << endl;
}
template<class T> void output(const T &x, ostream &out = cerr) {
output(all(x), out);
}
template<class T> int chkmin(T &a, const T &b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
template<class T> int chkmax(T &a, const T &b) {
if (b > a) {
a = b;
return 1;
}
return 0;
}
struct min_st {
min_st() {}
vector<pair<ll, int> > t;
int n;
void build(const vector<ll> &h, int v, int tl, int tr) {
if (tl == tr) {
t[v] = {h[tl], tl};
} else {
int tm = (tl + tr) >> 1;
build(h, v * 2, tl, tm);
build(h, v * 2 + 1, tm + 1, tr);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
void init(const vector<ll> &h) {
n = h.size();
t.resize(4 * n);
build(h, 1, 0, n - 1);
}
pair<ll, int> get(int l, int r, int v, int tl, int tr) {
if (r < tl || tr < l) {
return {-1, -1};
}
if (l <= tl && tr <= r) {
return t[v];
} else {
int tm = (tl + tr) >> 1;
pair<ll, int> res_l = get(l, r, v * 2, tl, tm);
pair<ll, int> res_r = get(l, r, v * 2 + 1, tm + 1, tr);
return max(res_l, res_r);
}
}
pair<ll, int> get(int l, int r) {
pair<ll, int> res = get(l, r, 1, 0, n - 1);
return res;
}
};
struct bridge {
int l, r;
ll y;
};
const ll INF = 1e18;
int n, m;
vector<ll> x, h;
vector<bridge> E;
map<ll, ll> mp;
vector<vector<pair<int, ll> > > events;
ll solve(int s, int g) {
events.resize(n);
for (int i = 0; i < E.size(); ++i) {
events[E[i].l].emplace_back(0, E[i].y);
events[E[i].r].emplace_back(1, E[i].y);
}
ll ans = INF;
set<int> new_chel;
int it = 0;
for (int i = 0; i < n; ++i) {
sort(all(events[i]));
new_chel.clear();
for (auto pp : events[i]) {
it++;
ll y = pp.second;
if (pp.first == 0) {
// cerr << "insert " << y << endl;
new_chel.insert(y);
auto it = mp.lower_bound(y);
ll val = INF;
if (i == 0) {
val = y;
}
if (it != mp.end()) {
chkmin(val, it->second + it->first - y);
}
if (it != mp.begin()) {
it--;
chkmin(val, it->second + y - it->first);
}
mp[y] = val;
// cerr << "dp = " << val << endl;
} else {
if (new_chel.find(y) != new_chel.end()) {
continue;
}
// cerr << "erase " << y << endl;
auto it = mp.find(y);
assert(it != mp.end());
if (next(it) != mp.end()) {
ll y1 = next(it)->first;
chkmin(mp[y1], mp[y] + y1 - y);
}
if (it != mp.begin()) {
ll y1 = prev(it)->first;
chkmin(mp[y1], mp[y] + y - y1);
}
if (i == n - 1) {
chkmin(ans, it->first + it->second + x[n - 1] - x[0]);
}
mp.erase(it);
}
}
// cerr << "i = " << i << endl;
// for (auto pp : mp) {
// cerr << pp.first << " " << pp.second << endl;
// }
}
for (auto pp : mp) {
chkmin(ans, pp.first + pp.second);
}
if (ans == INF) {
ans = -1;
}
return ans;
}
namespace djkstra_sol {
vector<vector<ll> > good_y;
vector<vector<pair<int, int> > > fwd, bck;
min_st T;
void add(int l, int r, ll x, vector<int> &res) {
if (l > r) {
return;
}
pair<ll, int> opt = T.get(l, r);
// cerr << "opt = " << opt.first << " " << opt.second << endl;
if (opt.first >= x) {
// cerr << "add " << opt.second << endl;
res.push_back(opt.second);
add(l, opt.second - 1, x, res);
add(opt.second + 1, r, x, res);
}
}
vector<int> find_x(bridge B) {
// cerr << "find_x " << B.l << " " << B.r << " " << B.y << endl;
vector<int> res;
add(B.l, B.r, B.y, res);
return res;
}
vector<vector<int> > xc;
void build_xc(int s, int g) {
T.init(h);
// output(all(h));
// cerr << "sg = " << s << " " << g << endl;
xc.resize(m);
good_y.resize(n);
for (int i = 0; i < m; ++i) {
xc[i] = find_x(E[i]);
sort(all(xc[i]));
for (auto id : xc[i]) {
good_y[id].push_back(E[i].y);
}
}
good_y[s].push_back(0);
good_y[g].push_back(0);
for (int i = 0; i < n; ++i) {
sort(all(good_y[i]));
good_y[i].erase(unique(all(good_y[i])), good_y[i].end());
}
}
void build_graph() {
fwd.resize(n);
bck.resize(n);
for (int i = 0; i < n; ++i) {
fwd[i].resize(good_y[i].size(), make_pair(-1, -1));
bck[i].resize(good_y[i].size(), make_pair(-1, -1));
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < (int)xc[i].size() - 1; ++j) {
int l = xc[i][j], r = xc[i][j + 1];
int pl = lower_bound(all(good_y[l]), E[i].y) - good_y[l].begin();
int pr = lower_bound(all(good_y[r]), E[i].y) - good_y[r].begin();
fwd[l][pl] = {r, pr};
bck[r][pr] = {l, pl};
}
}
}
const ll INF = 1e18;
vector<vector<ll> > d;
vector<vector<int> > used;
void djkstra(int s) {
d.resize(n);
used.resize(n);
for (int i = 0; i < n; ++i) {
d[i].resize(good_y[i].size(), INF);
used[i].resize(good_y[i].size(), 0);
}
set<pair<ll, pair<int, int> > > S;
d[s][0] = 0;
S.insert({0, {s, 0}});
vector<pair<ll, pair<int, int> > > go;
while (!S.empty()) {
int id = S.begin()->second.first;
int level = S.begin()->second.second;
S.erase(S.begin());
if (used[id][level]) {
continue;
}
used[id][level] = 1;
go.clear();
if (fwd[id][level] != make_pair(-1, -1)) {
go.emplace_back(x[fwd[id][level].first] - x[id], fwd[id][level]);
}
if (bck[id][level] != make_pair(-1, -1)) {
go.emplace_back(x[id] - x[bck[id][level].first], bck[id][level]);
}
if (level < (int)good_y[id].size() - 1) {
go.emplace_back(good_y[id][level + 1] - good_y[id][level], make_pair(id, level + 1));
}
if (level > 0) {
go.emplace_back(good_y[id][level] - good_y[id][level - 1], make_pair(id, level - 1));
}
for (auto ppp : go) {
if (chkmin(d[ppp.second.first][ppp.second.second], d[id][level] + ppp.first)) {
S.insert({d[ppp.second.first][ppp.second.second], ppp.second});
}
}
}
}
ll solve(int s, int g) {
build_xc(s, g);
// cerr << "build_xc" << endl;
build_graph();
djkstra(s);
return (d[g][0] == INF ? -1 : d[g][0]);
}
}
ll min_distance(vector<int> _x, vector<int> _h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
n = _x.size();
x.resize(n);
h.resize(n);
for (int i = 0; i < n; ++i) {
x[i] = (ll)_x[i];
h[i] = (ll)_h[i];
}
m = l.size();
for (int i = 0; i < m; ++i) {
E.push_back({l[i], r[i], y[i]});
}
ll res;
if (s == 0 && g == n - 1) {
res = solve(s, g);
} else {
res = djkstra_sol::solve(s, g);
}
return res;
}
