#include "walk.h"
#include <set>
#include <iostream>
#include <vector>
#include <queue>
using ll = long long;
using namespace std;
int n, m;
int cn = 0;
struct Li{
int l, r, h;
} ni[300099];
int na[100099][3];
int x[100099], h[100099], l[100099], r[100099], y[100099], s, g;
ll dst[300099][2];
struct HH{
int nd, h;
bool operator <(const HH &a) const{
if(h == a.h) return nd < a.nd;
else return h < a.h;
}
};
set <HH> se;
vector <HH> pr[100099], de[100099];
struct Segt{
int tr[400099];
void build(int node, int s, int e){
if(s == e){
tr[node] = h[s];
return;
}
int m = (s + e) / 2;
build(node * 2, s, m);
build(node * 2 + 1, m + 1, e);
tr[node] = max(tr[node * 2], tr[node * 2 + 1]);
}
int qry(int node, int s, int e, int qs, int qe){
if(qe < s || e < qs) return -1;
if(qs <= s && e <= qe) return tr[node];
int m = (s + e) / 2;
return max(qry(node * 2, s, m, qs, qe), qry(node * 2 + 1, m + 1, e, qs, qe));
}
} seg;
struct Ed{
int u;
ll v;
bool operator <(const Ed &a) const{
return v > a.v;
}
};
vector <Ed> gr[300099], b[300099], ps[300099], pg[300099]; //g -> 불변, b -> 변
int fs(int l, int r, int v){ //[l, r] 구간에서 v이상인 원소의 최소 위치
int s = l, e = r;
while(s <= e){
int m = (s + e) / 2;
if(seg.qry(1, 1, n, l, m) >= v) e = m - 1;
else s = m + 1;
}
return s;
}
int fe(int l, int r, int v){
int s = l, e = r;
while(s <= e){
int m = (s + e) / 2;
if(seg.qry(1, 1, n, m, r) >= v) s = m + 1;
else e = m - 1;
}
return e;
}
void dijk(int t, int k){
priority_queue <Ed> pq;
for(int i = 1; i <= cn; i ++){
if(ni[i].l == k || ni[i].r == k){
pq.push({i, ni[i].h});
dst[i][t] = ni[i].h;
}
}
while(pq.size()){
Ed to = pq.top();
if(dst[to.u][t] > to.v) continue;
pq.pop();
for(Ed &e : gr[to.u]){
if(dst[e.u][t] > e.v + to.v){
dst[e.u][t] = e.v + to.v;
pq.push({e.u, e.v + to.v});
}
}
for(Ed &e : b[to.u]){
if(e.u && dst[e.u][t] > e.v + to.v){
dst[e.u][t] = e.v + to.v;
pq.push({e.u, e.v + to.v});
}
}
}
}
ll min_distance(vector<int> xin, vector<int> hin, vector<int> lin, vector<int> rin, vector<int> yin, int sin, int gin){
n = xin.size(); m = lin.size();
for(int i = 0; i < n; i ++) x[i + 1] = xin[i];
for(int i = 0; i < n; i ++) h[i + 1] = hin[i];
for(int i = 0; i < m; i ++) l[i + 1] = lin[i] + 1;
for(int i = 0; i < m; i ++) r[i + 1] = rin[i] + 1;
for(int i = 0; i < m; i ++) y[i + 1] = yin[i];
s = sin + 1, g = gin + 1;
if(s > g) swap(s, g);
seg.build(1, 1, n);
for(int i = 1; i <= m; i ++){
int p, q;
p = fs(l[i], min(s, r[i]), y[i]);
q = fe(l[i], min(s, r[i]), y[i]);
if(p <= q){
ni[++cn] = {p, q, y[i]};
na[i][0] = cn;
}
p = fs(max(s, l[i]), min(g, r[i]), y[i]);
q = fe(max(s, l[i]), min(g, r[i]), y[i]);
if(p <= q){
ni[++cn] = {p, q, y[i]};
na[i][1] = cn;
}
p = fs(max(l[i], g), r[i], y[i]);
q = fe(max(l[i], g), r[i], y[i]);
if(p <= q){
ni[++cn] = {p, q, y[i]};
na[i][2] = cn;
}
}
for(int i = 1; i <= cn; i ++){
pr[ni[i].l].push_back({i, ni[i].h});
de[ni[i].r].push_back({i, ni[i].h});
}
for(int i = 1; i <= n; i ++){
for(HH &e : pr[i]){
auto it = se.lower_bound(e);
if(it != se.end()){
gr[it->nd].push_back({e.nd, it->h - e.h});
gr[e.nd].push_back({it->nd, it->h - e.h});
}
if(it != se.begin()){
it --;
gr[it->nd].push_back({e.nd, e.h - it->h});
gr[e.nd].push_back({it->nd, e.h - it->h});
}
se.insert(e);
}
for(HH &e : de[i]){
auto it = se.lower_bound(e);
it ++;
bool fl = (it != se.end());
it --;
if(fl == true && it != se.begin()){
it --;
auto pit = it;
it ++;
it ++;
auto ait = it;
it --;
gr[pit->nd].push_back({ait->nd, ait->h - pit->h});
gr[ait->nd].push_back({pit->nd, ait->h - pit->h});
}
se.erase(e);
}
}
for(int i = 0; i <= cn; i ++){
for(int j = 0; j < 2; j ++){
dst[i][j] = 1234567890123456789;
}
}
for(int i = 1; i <= m; i ++){
int p = na[i][0], q = na[i][1], r = na[i][2];
ps[p].push_back({q, (x[s] - x[ni[p].r]) * 2});
ps[p].push_back({r, (x[s] - x[ni[p].r]) * 2});
ps[q].push_back({r, 0});
ps[q].push_back({p, (x[ni[q].l] - x[s]) * 2});
ps[r].push_back({p, (x[ni[r].l] - x[s]) * 2});
}
for(int i = 1; i <= m; i ++){
int p = na[i][0], q = na[i][1], r = na[i][2];
pg[r].push_back({q, (x[ni[r].l] - x[g]) * 2});
pg[r].push_back({p, (x[ni[r].l] - x[g]) * 2});
pg[q].push_back({p, 0});
pg[q].push_back({r, (x[g] - x[ni[q].r]) * 2});
pg[p].push_back({r, (x[g] - x[ni[p].r]) * 2});
}
for(int i = 1; i <= cn; i ++) b[i] = ps[i];
dijk(0, s);
for(int i = 1; i <= cn; i ++) b[i] = pg[i];
dijk(1, g);
ll mi = 1234567890123456789;
for(int i = 1; i <= m; i ++){
int p = na[i][0], q = na[i][1], r = na[i][2];
if(p && q){
mi = min(mi, dst[p][0] + dst[q][1] + x[g] - x[ni[p].r] + x[s] - x[ni[p].r]);
}
if(p && r){
mi = min(mi, dst[p][0] + dst[r][1] + x[g] - x[ni[p].r] + x[s] - x[ni[p].r] + (x[ni[r].l] - x[g]) * 2);
}
}
if(mi <= 1000000000000000000) return mi;
else return -1;
}
