#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<pii> cc;
vector<vector<int>> skywalk(n);
cc.push_back({start, 0});
cc.push_back({end, 0});
skywalk[start].push_back(0);
skywalk[end].push_back(0);
for(int i = 0 ; i < m ; i++)
{
for(int j = L[i] ; j <= R[i] ; j++)
{
if(h[j] >= y[i])
{
cc.push_back({j, y[i]});
skywalk[j].push_back(y[i]);
}
}
}
sort(cc.begin(), cc.end());
cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
vector<vector<pair<int, ll>>> g(cc.size());
for(int i = 0 ; i < n ; i++)
{
sort(skywalk[i].begin(), skywalk[i].end());
for(int j = 0 ; j + 1 < skywalk[i].size() ; j++)
{
int a = lower_bound(cc.begin(), cc.end(), (pii){i, skywalk[i][j]}) - cc.begin(),
b = lower_bound(cc.begin(), cc.end(), (pii){i, skywalk[i][j+1]}) - cc.begin();
ll w = skywalk[i][j+1] - skywalk[i][j];
g[a].push_back({b, w});
g[b].push_back({a, w});
}
}
for(int i = 0 ; i < m ; i++)
{
int a = -1;
for(int j = L[i] ; j <= R[i] ; j++)
{
if(h[j] >= y[i])
{
if(a == -1)
{
a = lower_bound(cc.begin(), cc.end(), (pii){j, y[i]}) - cc.begin();
}
else
{
int b = lower_bound(cc.begin(), cc.end(), (pii){j, y[i]}) - cc.begin();
ll w = x[cc[b].first] - x[cc[a].first];
g[a].push_back({b, w});
g[b].push_back({a, w});
a = b;
}
}
}
}
priority_queue<pair<ll, int>> q;
int s = lower_bound(cc.begin(), cc.end(), (pii){start, 0}) - cc.begin();
q.push({0, s});
vector<bool> flag(cc.size());
vector<ll> dp(cc.size(), INFLL);
dp[s] = 0;
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 = lower_bound(cc.begin(), cc.end(), (pii){end, 0}) - cc.begin();
return (dp[e] == INFLL ? -1 : dp[e]);
}
