#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int f) {
int n = (int) x.size();
int m = (int) y.size();
vector<pair<int, int>> ver;
for (int i = 0; i < n; i++) {
ver.emplace_back(i, 0);
ver.emplace_back(i, h[i]);
}
for (int i = 0; i < m; i++) {
ver.emplace_back(l[i], y[i]);
ver.emplace_back(r[i], y[i]);
}
vector<vector<int>> qs(n);
for (int i = 0; i < m; i++) {
qs[l[i]].push_back(y[i]);
qs[r[i]].push_back(~y[i]);
}
multiset<int> st;
for (int i = 0; i < n; i++) {
for (int j : qs[i]) {
if (j >= 0) {
auto it = st.lower_bound(j);
if (it != st.end()) {
ver.emplace_back(i, *it);
}
if (it != st.begin()) {
ver.emplace_back(i, *prev(it));
}
st.insert(j);
}
}
for (int j : qs[i]) {
if (j < 0) {
j = ~j;
auto it = st.lower_bound(j);
if (it != prev(st.end())) {
ver.emplace_back(i, *next(it));
}
if (it != st.begin()) {
ver.emplace_back(i, *prev(it));
}
st.erase(it);
}
}
}
vector<pair<int, int>> new_ver;
for (auto& p : ver) {
if (h[p.first] >= p.second) {
new_ver.push_back(p);
}
}
ver = new_ver;
sort(ver.begin(), ver.end());
ver.erase(unique(ver.begin(), ver.end()), ver.end());
auto Index = [&](int i, int h) {
return (int) (lower_bound(ver.begin(), ver.end(), make_pair(i, h)) - ver.begin());
};
int k = (int) ver.size();
vector<vector<pair<int, int>>> g(k);
auto Add = [&](int from, int to, int cost) {
g[from].emplace_back(to, cost);
g[to].emplace_back(from, cost);
};
for (int i = 0; i + 1 < k; i++) {
if (ver[i + 1].first == ver[i].first) {
Add(i, i + 1, ver[i + 1].second - ver[i].second);
}
}
map<int, vector<int>> mp;
for (int i = 0; i < k; i++) {
mp[ver[i].second].push_back(i);
}
for (auto& p : mp) {
sort(p.second.begin(), p.second.end(), [&](int i, int j) {
return ver[i].first < ver[j].first;
});
}
for (int i = 0; i < m; i++) {
int low = 0, high = (int) mp[y[i]].size() - 1, pos = -1;
while (low <= high) {
int mid = (low + high) >> 1;
if (ver[mp[y[i]][mid]].first >= l[i]) {
pos = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
while (ver[mp[y[i]][pos]].first != r[i]) {
Add(mp[y[i]][pos], mp[y[i]][pos + 1], x[ver[mp[y[i]][pos + 1]].first] - x[ver[mp[y[i]][pos]].first]);
pos += 1;
}
}
const long long inf = (long long) 1e18;
vector<long long> dist(k, inf);
dist[Index(s, 0)] = 0;
set<pair<long long, int>> que;
que.emplace(0, Index(s, 0));
while (!que.empty()) {
auto it = que.begin();
int i = it->second;
que.erase(it);
for (auto &e : g[i]) {
int to = e.first;
int w = e.second;
if (dist[to] > dist[i] + w) {
if (dist[to] != inf) {
que.erase({dist[to], to});
}
dist[to] = dist[i] + w;
que.emplace(dist[to], to);
}
}
}
long long res = dist[Index(f, 0)];
if (res == inf) {
return -1;
} else {
return res;
}
}
