#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const ll INFLL = 1e18;
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 start, int end) {
int n = x.size(),
m = y.size();
vector<vector<int>> rmq(h.size(), vector<int> (18));
for(int i = 0 ; i < h.size() ; i++)
rmq[i][0] = h[i];
for(int i = 1 ; (1<<i) < n ; i++)
{
for(int j = 0 ; j + (1<<i) - 1 < n ; j++)
{
rmq[j][i] = max(rmq[j][i-1], rmq[j+(1<<(i-1))][i-1]);
}
};
function<int(int, int)> query = [&](int l, int r)
{
int lg = __lg(r - l + 1);
return max(rmq[l][lg], rmq[r-(1<<lg)+1][lg]);
};
vector<pii> cc;
vector<vector<int>> d(n);
d[start].push_back(0);
d[end].push_back(0);
cc.push_back({x[start], 0});
cc.push_back({x[end], 0});
for(int i = 0 ; i < m ; i++)
{
int L = l[i];
cc.push_back({x[l[i]], y[i]});
d[l[i]].push_back(y[i]);
while(l[i] < r[i])
{
for(int j = 18 ; j >= 0 ; j--)
{
int target = l[i] + (1<<j);
if(target <= r[i] and query(l[i]+1, target) < y[i])
l[i] = target;
}
l[i]++;
cc.push_back({x[l[i]], y[i]});
d[l[i]].push_back(y[i]);
}
l[i] = L;
}
sort(cc.begin(), cc.end());
cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
function<int(int, int)> f = [&](int a, int b)
{
return lower_bound(cc.begin(), cc.end(), (pii){a, b}) - cc.begin();
};
vector<vector<pair<int, ll>>> g(cc.size());
for(int i = 0 ; i < m ; i++)
{
int last = l[i];
while(l[i] < r[i])
{
for(int j = 18 ; j >= 0 ; j--)
{
int target = l[i] + (1<<j);
if(target <= r[i] and query(l[i]+1, target) < y[i])
l[i] = target;
}
l[i]++;
int a = f(x[last], y[i]),
b = f(x[l[i]], y[i]),
w = x[l[i]] - x[last];
g[a].push_back({b, w});
g[b].push_back({a, w});
last = l[i];
}
}
for(int i = 0 ; i < n ; i++)
{
sort(d[i].begin(), d[i].end());
for(int j = 0 ; j + 1 < d[i].size() ; j++)
{
int a = f(x[i], d[i][j]),
b = f(x[i], d[i][j+1]),
w = d[i][j+1] - d[i][j];
g[a].push_back({b, w});
g[b].push_back({a, w});
}
}
priority_queue<pair<ll, int>> q;
vector<ll> dp(cc.size(), INFLL);
vector<bool> flag(cc.size());
int s = f(x[start], 0);
dp[s] = 0;
q.push({0, s});
while(q.size())
{
int nod = q.top().second;
q.pop();
if(flag[nod])
continue;
flag[nod] = true;
for(auto i: g[nod])
{
if(dp[i.first] > dp[nod] + i.second)
{
dp[i.first] = dp[nod] + i.second;
q.push({-dp[i.first], i.first});
}
}
}
int e = f(x[end], 0);
return (dp[e] == INFLL ? -1 : dp[e]);
}
