#include "walk.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
#define lsort(a) sort(iter(a))
using namespace std;
typedef long long ll;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
const ll MAX = 1LL << 60;
struct SegmentTree{
vector<ll> st;
void resize(int n){
st.resize(4 * n, MAX);
}
void modify(int pos, ll v, int L, int R, int id){
if(L == R){
st[id] = v;
return;
}
int M = (L + R) / 2;
if(pos <= M) modify(pos, v, L, M, 2 * id + 1);
else modify(pos, v, M + 1, R, 2 * id + 2);
st[id] = min(st[2 * id + 1], st[2 * id + 2]);
}
ll query(int l, int r, int L, int R, int id){
if(l == L && r == R){
return st[id];
}
int M = (L + R) / 2;
if(r <= M) return query(l, r, L, M, 2 * id + 1);
else if(l > M) return query(l, r, M + 1, R, 2 * id + 2);
else return min(query(l, M, L, M, 2 * id + 1), query(M + 1, r, M + 1, R, 2 * id + 2));
}
};
int n, m;
vector<int> x, h, tl, tr, ty;
int sv, gv;
SegmentTree pre, suf;
vector<int> discr;
int sz;
int dcr(int v){
return lower_bound(iter(discr), v) - discr.begin();
}
ll calc(int y){
return min(discr[y] + pre.query(0, y, 0, sz - 1, 0), -discr[y] + suf.query(y, sz - 1, 0, sz - 1, 0));
}
ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g){
x = _x; h = _h; tl = _l; tr = _r; ty = _y; sv = _s; gv = _g;
n = x.size();
m = ty.size();
assert(sv == 0 && gv == n - 1);
discr = ty;
discr.eb(0);
lsort(discr);
discr.resize(unique(iter(discr)) - discr.begin());
sz = discr.size();
pre.resize(sz);
suf.resize(sz);
vector<vector<int>> add(n), del(n);
for(int i = 0; i < m; i++){
add[tl[i]].eb(dcr(ty[i]));
del[tr[i]].eb(dcr(ty[i]));
}
del[0].eb(0);
pre.modify(0, 0, 0, sz - 1, 0);
suf.modify(0, 0, 0, sz - 1, 0);
vector<bool> use(sz);
for(int i = 0; i < n - 1; i++){
for(int j : add[i]){
use[j] = true;
ll v = calc(j);
if(v == MAX) continue;
//cerr << "test " << i << " " << discr[j] << " " << v << "\n";
pre.modify(j, v - discr[j], 0, sz - 1, 0);
suf.modify(j, v + discr[j], 0, sz - 1, 0);
}
for(int j : del[i]){
if(use[j]) continue;
pre.modify(j, MAX, 0, sz - 1, 0);
suf.modify(j, MAX, 0, sz - 1, 0);
}
for(int j : add[i]) use[j] = false;
//cerr << "test " << i << " ";
/*for(int j = 0; j < sz; j++){
cerr << pre.query(j, j, 0, sz - 1, 0) + discr[j] << " ";
}*/
//cerr << "\n";
}
ll v = calc(0);
if(v == MAX) return -1;
return v + x[n - 1] - x[0];
}
