#include <bits/stdc++.h>
#include "walk.h"
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 1e5 + 7;
const long long inf = 1e18;
long long dis[6 * N];
map<int, int> ma[N];
map<int, set<int>> se;
vector<int> ad[N], re[N];
vector<pair<long long, long long>> adj[6 * N];
inline void Edge(int x, int y, int w)
{
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int sta, int en)
{
int n = x.size(), m = l.size();
vector<int> v, gl(n, -1), gr(n, -1);
stack<int> st;
for (int i = 0; i < n; i++)
{
while (!st.empty() && h[st.top()] <= h[i])
st.pop();
if (!st.empty())
gl[i] = st.top();
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = n - 1; i >= 0; i--)
{
while (!st.empty() && h[st.top()] <= h[i])
st.pop();
if (!st.empty())
gr[i] = st.top();
st.push(i);
}
auto Do = [&](int z)
{
v.clear();
for (int i = 0; i < m; i++)
if (l[i] < z && z < r[i] && y[i] <= h[z])
{
l.push_back(z);
r.push_back(r[i]);
y.push_back(y[i]);
r[i] = z;
}
m = l.size();
for (int i = 0; i < m; i++)
if (l[i] < z && z < r[i] && y[i] > h[z])
v.push_back(i);
sort(all(v), [&](int a, int b)
{ return y[a] < y[b]; });
int le = z, ri = z;
for (int i = 0; i < v.size(); i++)
{
while (h[le] < y[v[i]])
le = gl[le];
while (h[ri] < y[v[i]])
ri = gr[ri];
if (le != l[v[i]])
{
l.push_back(l[v[i]]);
r.push_back(le);
y.push_back(y[v[i]]);
}
if (ri != r[v[i]])
{
l.push_back(ri);
r.push_back(r[v[i]]);
y.push_back(y[v[i]]);
}
l[v[i]] = le;
r[v[i]] = ri;
}
m = l.size();
};
Do(sta);
Do(en);
int cnt = 0;
ma[sta][0] = cnt++;
ma[en][0] = cnt++;
for (int i = 0; i < m; i++)
{
if (ma[l[i]].find(y[i]) == ma[l[i]].end())
ma[l[i]][y[i]] = cnt++;
if (ma[r[i]].find(y[i]) == ma[r[i]].end())
ma[r[i]][y[i]] = cnt++;
ad[l[i]].push_back(y[i]);
re[r[i]].push_back(y[i]);
se[y[i]].insert(l[i]);
se[y[i]].insert(r[i]);
}
multiset<int> t;
t.insert(0);
for (int i = 0; i < n; i++)
{
for (auto it : ad[i])
t.insert(it);
auto down = [&](int it)
{
int z = *(--t.lower_bound(it));
if (ma[i].find(z) == ma[i].end())
ma[i][z] = cnt++;
Edge(ma[i][it], ma[i][z], it - z);
se[z].insert(i);
};
for (auto it : ad[i])
down(it);
for (auto it : re[i])
down(it);
for (auto it : re[i])
t.erase(t.find(it));
}
for (int i = 0; i < m; i++)
{
auto p = se[y[i]].find(l[i]);
int la = l[i];
++p;
while (p != se[y[i]].end() && *p <= r[i])
{
Edge(ma[la][y[i]], ma[*p][y[i]], x[*p] - x[la]);
la = *p;
++p;
}
}
for (int i = 1; i < cnt; i++)
dis[i] = inf;
set<pair<long long, long long>> s;
s.insert({0, 0});
while (!s.empty())
{
auto p = s.begin();
int xx = p->second;
s.erase(p);
for (auto yy : adj[xx])
{
if (dis[xx] + yy.second < dis[yy.first])
{
if (dis[yy.first] != inf)
s.erase({dis[yy.first], yy.first});
dis[yy.first] = dis[xx] + yy.second;
s.insert({dis[yy.first], yy.first});
}
}
}
if (dis[1] == inf)
return -1;
return dis[1];
}
