#include "walk.h"
#include <bits/stdc++.h>
#define int int64_t
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define ii pair<int, int>
#define vii vector<ii>
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define loop(i,s,e) for(int i=s;i<e;++i)
#define chkmin(a,b) a = min(a,b)
using namespace std;
const int INF = 2e18;
struct SEG{
int l,r,mid;
multiset<int> vs;
int vp = INF, vm = INF;
SEG *lp=0, *rp=0;
SEG(int l, int r): l(l), r(r), mid((l+r)/2){
if (l+1==r) vs.insert(INF);
}
void fix(){
if (!lp) lp = new SEG(l, mid);
if (!rp) rp = new SEG(mid, r);
vp = min(lp->vp, rp->vp);
vm = min(lp->vm, rp->vm);
}
void update(int i, int v, bool in){
if (l+1==r){
if (in){
vs.insert(v);
}
else{
vs.erase(vs.find(v));
}
int vv = *vs.begin();
vp = vv + l;
vm = vv - l;
return ;
}
fix();
if (i<mid) lp->update(i, v, in);
else rp->update(i, v, in);
fix();
}
int query(int a, int b, bool plus){
if (a>=r || b<=l) return INF;
if (a<=l && r<=b) return (plus?vp:vm);
fix();
return min(lp->query(a,b,plus), rp->query(a,b,plus));
}
};
long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g) {
int n = x.size(), m = l.size();
vvi in(n), out(n);
loop(i,0,m){
in[l[i]].pb(i);
out[r[i]].pb(i);
}
SEG seg(0, 2e9);
seg.update(0,-x[0],1);
vi vals(m);
int ans;
loop(pos,0,n){
for(auto i:in[pos]){
int v = INF;
chkmin(v, y[i] + seg.query(0, y[i], 0));
chkmin(v, seg.query(y[i], h[pos]+1, 1) - y[i]);
//v+=x[pos];
vals[i] = v;
//vals.pb({y[i], v});
seg.update(y[i], vals[i], 1);
}
ans = seg.query(0, h[pos]+1, 1) + x[pos];
for(auto i:out[pos]){
seg.update(y[i], vals[i], 0);
}
if (pos==0){
seg.update(0, -x[0],0);
}
}
if (ans>INF/2) ans = -1;
return ans;
}
/*
clear
g++ grader.cpp walk.cpp -o a ; ./a
7 5
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
2 3 1
3 4 2
4 6 5
0 6
2 1
0 2
1 2
0 1 2
0 1
*/
