#include <bits/stdc++.h>
#include "walk.h"
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 100100;
const ll OO = 1e18;
vector<int> vc, real_y;
vector<array<int, 3> > lines;
vector<pii> events[N];
int n, m, pos;
bool fd;
ll st[4 * N], psh[4 * N], ans = OO, gt_vl;
void build(int v, int l, int r){
psh[v] = 0;
st[v] = OO;
if (l == r) return;
int md = (l + r) >> 1;
build(v + v, l, md);
build(v + v + 1, md + 1, r);
}
void push(int v){
if (psh[v] != 0){
st[v] += psh[v];
if (v + v + 1 < 4 * N){
psh[v + v] += psh[v];
psh[v + v + 1] += psh[v];
}
psh[v] = 0;
}
}
void update(int v, int l, int r, int ps, ll vl){
push(v);
if (l == r){
st[v] = vl;
return;
}
int md = (l + r) >> 1;
if (ps <= md)
update(v + v, l, md, ps, vl);
else update(v + v + 1, md + 1, r, ps, vl);
push(v + v);
push(v + v + 1);
st[v] = min(st[v + v], st[v + v + 1]);
}
void add(int v, int tl, int tr, int l, int r, ll vl){
push(v);
if (l > r) return;
if (tl == l && tr == r){
psh[v] += vl;
push(v);
return;
}
int md = (tl + tr) >> 1;
add(v + v, tl, md, l, min(r, md), vl);
add(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);
st[v] = min(st[v + v], st[v + v + 1]);
}
void real_search_left(int v, int l, int r){
push(v);
if (l == r){
fd = 1;
pos = l;
gt_vl = st[v];
return;
}
push(v + v);
push(v + v + 1);
int md = (l + r) >> 1;
if (st[v + v + 1] < OO)
real_search_left(v + v + 1, md + 1, r);
else real_search_left(v + v, l, md);
}
void search_left(int v, int tl, int tr, int l, int r){
push(v);
if (fd || l > r) return;
if (tl == l && tr == r){
if (st[v] < OO)
real_search_left(v, l, r);
return;
}
int md = (tl + tr) >> 1;
search_left(v + v + 1, md + 1, tr, max(md + 1, l), r);
search_left(v + v, tl, md, l, min(r, md));
}
void real_search_right(int v, int l, int r){
push(v);
if (l == r){
fd = 1;
pos = l;
gt_vl = st[v];
return;
}
push(v + v);
push(v + v + 1);
int md = (l + r) >> 1;
if (st[v + v] < OO)
real_search_right(v + v, l, md);
else real_search_right(v + v + 1, md + 1, r);
}
void search_right(int v, int tl, int tr, int l, int r){
push(v);
if (fd || l > r) return;
if (tl == l && tr == r){
if (st[v] < OO)
real_search_right(v, l, r);
return;
}
int md = (tl + tr) >> 1;
search_right(v + v, tl, md, l, min(r, md));
search_right(v + v + 1, md + 1, tr, max(md + 1, l), r);
}
void get_ans(int v, int l, int r){
push(v);
if (l == r){
if (st[v] < OO)
ans = min(ans, st[v] + ll(real_y[l]));
return;
}
int md = (l + r) >> 1;
get_ans(v + v, l, md);
get_ans(v + v + 1, md + 1, r);
}
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) {
lines.clear();
n = sz(x); m = sz(l);
vc.clear();
for (int i = 0; i < m; i++)
real_y.PB(y[i]);
sort(all(real_y));
real_y.resize(unique(all(real_y)) - real_y.begin());
// for (int cr : real_y)
// cerr << cr << " "; cerr << '\n';
for (int i = 0; i < m; i++){
y[i] = lower_bound(all(real_y), y[i]) - real_y.begin();
}
for (int i = 0; i < m; i++)
lines.PB({y[i], l[i], r[i]});
sort(all(lines));
for (int i = 0; i < m; ){
int j = i;
while (j < m && lines[j][0] == lines[i][0])
j++;
pii seg = MP(lines[i][1], lines[i][2]);
int ht = lines[i][0];
for (int I = i + 1; I < j; I++)
if (seg.sd < lines[I][1]){
events[seg.ft].PB(MP(-1, ht));
events[seg.sd].PB(MP(+1, ht));
seg = MP(lines[I][1], lines[I][2]);
} else seg.sd = max(lines[I][2], seg.sd);
events[seg.ft].PB(MP(-1, ht));
events[seg.sd].PB(MP(+1, ht));
i = j;
}
build(1, 0, sz(real_y) - 1);
for (pii cr : events[0]){
int ht = cr.sd;
update(1, 0, sz(real_y) - 1, ht, real_y[ht]);
}
add(1, 0, sz(real_y) - 1, 0, sz(real_y) - 1, x[1] - x[0]);
for (int loc = 1; loc < n - 1; loc++){
sort(all(events[loc]));
for (pii cr : events[loc]){
int ht = cr.sd;
if (cr.ft > 0){
update(1, 0, sz(real_y) - 1, ht, OO);
} else {
push(1);
if (st[1] == OO) return -1;
ll best = OO;
fd = 0; pos = -1; gt_vl = -1;
search_left(1, 0, sz(real_y) - 1, 0, ht - 1);
if (fd){
best = min(best, gt_vl + ll(real_y[ht]) - ll(real_y[pos]));
}
fd = 0; pos = -1; gt_vl = -1;
search_right(1, 0, sz(real_y) - 1, ht + 1, sz(real_y) - 1);
if (fd){
best = min(best, gt_vl - ll(real_y[ht]) + ll(real_y[pos]));
}
if (best == OO) return -1;
// assert(best != OO);
// if (best == OO){
// while (1) {}
// }
update(1, 0, sz(real_y) - 1, ht, best);
}
}
add(1, 0, sz(real_y) - 1, 0, sz(real_y) - 1, x[loc + 1] - x[loc]);
}
get_ans(1, 0, sz(real_y) - 1);
return (ans == OO ? -1 : ans);
}
