#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const ll INF = 1e15;
struct Build
{
int X, H;
};
struct Line
{
int L, R, Y;
};
int N, M, S, E;
Build A[MAXN+10];
Line B[MAXN+10];
vector<int> V[MAXN+10];
vector<ll> dist[MAXN+10];
vector<pii> L[MAXN+10], R[MAXN+10];
struct Queue
{
int x, y; ll w;
bool operator < (const Queue &p) const
{
return w>p.w;
}
};
ll min_distance(vector<int> _X, vector<int> _H, vector<int> _L, vector<int> _R, vector<int> _Y, int _S, int _E)
{
N=_X.size(); M=_L.size();
for(int i=0; i<N; i++) A[i+1]={_X[i], _H[i]};
for(int i=0; i<M; i++) B[i+1]={_L[i]+1, _R[i]+1, _Y[i]};
S=_S+1; E=_E+1;
for(int i=1; i<=N; i++) V[i].push_back(0);
for(int i=1; i<=M; i++)
{
for(int j=B[i].L; j<=B[i].R; j++)
{
if(B[i].Y<=A[j].H)
{
V[j].push_back(B[i].Y);
}
}
}
for(int i=1; i<=N; i++)
{
sort(V[i].begin(), V[i].end());
dist[i]=vector<ll>(V[i].size(), INF);
L[i]=vector<pii>(V[i].size(), pii(0, 0));
R[i]=vector<pii>(V[i].size(), pii(N+1, 0));
}
for(int i=1; i<=M; i++)
{
int by=lower_bound(V[B[i].L].begin(), V[B[i].L].end(), B[i].Y)-V[B[i].L].begin(), bx=B[i].L;
for(int j=B[i].L+1; j<=B[i].R; j++)
{
if(B[i].Y<=A[j].H)
{
int y=lower_bound(V[j].begin(), V[j].end(), B[i].Y)-V[j].begin(), x=j;
L[x][y]=pii(bx, by);
R[bx][by]=pii(x, y);
by=y; bx=x;
}
}
}
priority_queue<Queue> PQ;
PQ.push({S, 0, 0});
while(!PQ.empty())
{
Queue now=PQ.top(); PQ.pop();
if(dist[now.x][now.y]<=now.w) continue;
dist[now.x][now.y]=now.w;
if(now.y+1<V[now.x].size()) PQ.push({now.x, now.y+1, now.w+V[now.x][now.y+1]-V[now.x][now.y]});
if(now.y-1>=0) PQ.push({now.x, now.y-1, now.w+V[now.x][now.y]-V[now.x][now.y-1]});
if(L[now.x][now.y].first>=1) PQ.push({L[now.x][now.y].first, L[now.x][now.y].second, now.w+A[now.x].X-A[L[now.x][now.y].first].X});
if(R[now.x][now.y].first<=N) PQ.push({R[now.x][now.y].first, R[now.x][now.y].second, now.w-A[now.x].X+A[R[now.x][now.y].first].X});
}
if(dist[E][0]==INF) return -1;
return dist[E][0];
}
