#include "walk.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
typedef long long ll;
const ll inf = 1e16;
using namespace std;
struct BIT{
vector<ll> bit;
int n;
BIT(int _n){
n = _n;
bit.resize(n + 1);
fill(bit.begin(), bit.end(), inf);
}
void modify(int pos, ll val){
while(pos <= n){
bit[pos] = min(bit[pos], val);
pos += (pos & -pos);
}
}
int query(int pos){
ll ans = inf;
while(pos > 0){
ans = min(ans, bit[pos]);
pos -= (pos & -pos);
}
return ans;
}
};
struct st{
vector<ll> seg;
st(int n){
seg.resize(4 * n + 4);
fill(seg.begin(), seg.end(), inf);
}
void modify(int l, int r, int pos, ll num, int ind){
if(l == r){
seg[ind] = num;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) modify(l, mid, pos, num, ind * 2);
else modify(mid + 1, r, pos, num, ind * 2 + 1);
seg[ind] = min(seg[ind * 2], seg[ind * 2 + 1]);
}
ll query(int l, int r, int start, int end, int ind){
if(r < start || end < l) return inf;
if(start <= l && r <= end) return seg[ind];
int mid = (l + r) >> 1;
return min(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
}
};
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) {
vector<ll> cp;
int n = (int)x.size(), m = (int)l.size();
for(int i = 0; i < n; i++) cp.push_back(h[i]);
for(int i = 0; i < m; i++) cp.push_back(y[i]);
cp.push_back(0);
sort(cp.begin(), cp.end());
cp.resize(unique(cp.begin(), cp.end()) - cp.begin());
for(auto &xx: h){
xx = lower_bound(cp.begin(), cp.end(), xx) - cp.begin() + 1;
}
for(auto &xx: y){
xx = lower_bound(cp.begin(), cp.end(), xx) - cp.begin() + 1;
}
vector<vector<int>> in(n), out(n);
vector<ll> lst(m);
for(int i = 0; i < m; i++){
in[l[i]].push_back(i);
out[r[i]].push_back(i);
}
int sz = (int)cp.size();
if(s == 0 && g == n - 1){
// cp[pos - 1]
st cis(sz);
st trans(sz);
cis.modify(1, sz, 1, 0, 1);
trans.modify(1, sz, 1, 0, 1);
cp.insert(cp.begin(), 0);
for(int i = 0; i < n; i++){
vector<ll> dps((int)in[i].size());
int cnt = 0;
for(auto &id: in[i]){
ll dp = inf;
dp = min(dp, cis.query(1, sz, 1, y[id], 1) + cp[y[id]]);
if(h[i] > y[id]) dp = min(dp, trans.query(1, sz, y[id], h[i], 1) - cp[y[id]]);
dps[cnt] = dp;
cnt++;
}
if(i < n - 1) for(auto &id: out[i]){
cis.modify(1, sz, y[id], inf, 1);
trans.modify(1, sz, y[id], inf, 1);
}
if(i == 0){
cis.modify(1, sz, 1, inf, 1);
trans.modify(1, sz, 1, inf, 1);
}
cnt = 0;
for(auto &id: in[i]){
cis.modify(1, sz, y[id], dps[cnt] - cp[y[id]], 1);
trans.modify(1, sz, y[id], dps[cnt] + cp[y[id]], 1);
cnt++;
}
}
ll ans = inf;
for(int i = 1; i <= sz; i++){
ans = min(ans, cis.query(1, sz, i, i, 1) + cp[i] + cp[i]);
ans = min(ans, trans.query(1, sz, i, i, 1));
//cout << i << " " << cis.query(1, sz, i, i, 1) + cp[i] << " " << trans.query(1, sz, i, i, 1) - cp[i] << "\n";
}
return ans + x[n - 1] - x[0];
}
return 1;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp walk.cpp
