#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;
}
};
struct SEG
{
vector<pii> tree[MAXN*4+10];
void init(int node, int tl, int tr)
{
if(tl==tr)
{
tree[node].push_back(pii(A[tl].H, tl));
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node].resize(tr-tl+1);
merge(tree[node*2].begin(), tree[node*2].end(), tree[node*2+1].begin(), tree[node*2+1].end(), tree[node].begin(), greater<pii>());
}
void get(int node, int tl, int tr, int l, int r, int x, vector<int> &V)
{
if(l<=tl && tr<=r)
{
for(auto it : tree[node])
{
if(it.first<x) break;
V.push_back(it.second);
}
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
get(node*2, tl, mid, l, r, x, V);
get(node*2+1, mid+1, tr, l, r, x, V);
}
}seg;
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;
seg.init(1, 1, N);
for(int i=1; i<=N; i++) V[i].push_back(0);
for(int i=1; i<=M; i++)
{
vector<int> T;
seg.get(1, 1, N, B[i].L, B[i].R, B[i].Y, T);
sort(T.begin(), T.end());
for(auto j : T)
{
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++)
{
vector<int> T;
seg.get(1, 1, N, B[i].L, B[i].R, B[i].Y, T);
sort(T.begin(), T.end());
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(auto j : T)
{
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];
}
