#include<bits/stdc++.h>
#include"walk.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 5;
const ll linf = 0x3f3f3f3f3f3f3f3f;

ll min_distance(vector<int> a, vector<int> h, vector<int> pl, vector<int> pr, vector<int> py, int beg, int enn)
{
	int n = (int)a.size(), m = (int)pl.size();
	
	vector< vector<int> > eff(n);
	for(int i=0; i<m; ++i)
	{
		eff[pl[i]].emplace_back(py[i]);
		eff[pr[i]].emplace_back(-py[i]);
	}
	
	vector< vector<int> > keys(n);
	for(int i=0; i<n; ++i)
	{
		keys[i].emplace_back(0);
		keys[i].emplace_back(h[i]);
	}
	for(int i=0; i<m; ++i)
	{
		keys[pl[i]].emplace_back(py[i]);
		keys[pr[i]].emplace_back(py[i]);
	}
	
	static int sta[MAXN];
	int tp = 0;
	auto getsta = [&] (int y)
	{
		int l = 0, r = tp;
		while(l<r)
		{
			int mid = (l+r+1)>>1;
			if(h[sta[mid]] >= y) l = mid;
			else r = mid-1;
		}
		return l? sta[l]: -1;
	};
	
	for(int i=0; i<n; ++i)
	{
		while(tp && h[sta[tp]] <= h[i]) --tp;
		sta[++tp] = i;
		
		if(i == beg || i == enn)
		{
			for(int j=0; j<m; ++j)
			{
				int v = getsta(py[j]);
				if(v != -1) keys[v].emplace_back(py[j]);
			}
		}
	}
	
	tp = 0;
	for(int i=n-1; i>=0; --i)
	{
		while(tp && h[sta[tp]] <= h[i]) --tp;
		sta[++tp] = i;
		
		if(i == beg || i == enn)
		{
			for(int j=0; j<m; ++j)
			{
				int v = getsta(py[j]);
				if(v != -1) keys[v].emplace_back(py[j]);
			}
		}
	}
	
	multiset<int> q;
	for(int i=0; i<n; ++i)
	{
		for(int t: eff[i]) if(t < 0)
			q.erase(q.find(-t));
		
		vector<int> nkeys;
		auto push = [&] (int x)
		{
			if(x <= h[i]) nkeys.emplace_back(x);
		};
		auto pushall = [&] (int x)
		{
			push(x);
			auto it = q.upper_bound(x);
			if(it != q.end()) push(*it);
			if(it != q.begin()) push(*prev(it));
		};
		
		for(int t: keys[i])
			pushall(t);
		if(i > 0) pushall(h[i-1] + 1);
		if(i+1 < n) pushall(h[i+1] + 1);
		
		keys[i].swap(nkeys);
		
		for(int t: eff[i]) if(t > 0)
			q.emplace(t);
	}
	
	vector< vector<int> > lef(n), rig(n);
	vector< vector<ll> > f(n);
	
	for(int i=0; i<n; ++i)
	{
		auto &vec = keys[i];
		sort(vec.begin(), vec.end());
		vec.erase(unique(vec.begin(), vec.end()), vec.end());
		
		lef[i].resize(vec.size(), -1);
		rig[i].resize(vec.size(), -1);
		f[i].resize(vec.size(), linf);
	}
	
	q.clear();
	map<int,int> bak;
	for(int i=0; i<n; ++i)
	{
		for(int j=0; j<(int)keys[i].size(); ++j)
			if(q.count(keys[i][j]))
				lef[i][j] = bak[keys[i][j]];
		
		for(int t: eff[i])
		{
			if(t > 0) q.emplace(t);
			else q.erase(q.find(-t));
		}
		
		for(auto t: keys[i])
			bak[t] = i;
		
		for(int j=0; j<(int)keys[i].size(); ++j)
			rig[i][j] = q.count(keys[i][j])? -2: -1;
	}
	
	bak.clear();
	for(int i=n-1; i>=0; --i)
	{
		for(int j=0; j<(int)keys[i].size(); ++j)
			if(rig[i][j] == -2)
				rig[i][j] = bak[keys[i][j]];
		
		for(auto t: keys[i])
			bak[t] = i;
	}
	
	priority_queue< tuple<ll,int,int> > qq;
	auto upd = [&] (int i,int j,ll k)
	{
		if(k >= f[i][j]) return;
		f[i][j] = k;
		qq.emplace(-k, i, j);
	};
	upd(beg, 0, 0);
	while(qq.size())
	{
		ll cur; int i,j;
		tie(cur,i,j) = qq.top(); qq.pop();
		cur *= -1;
		if(cur != f[i][j]) continue;
		
		int y = keys[i][j];
		
		if(j > 0)
			upd(i, j-1, cur + y - keys[i][j-1]);
		if(j+1 < (int)keys[i].size())
			upd(i, j+1, cur + keys[i][j+1] - y);
		
		auto trans = [&] (int v)
		{
			if(v == -1) return;
			auto it = lower_bound(keys[v].begin(), keys[v].end(), y);
			upd(v, it - keys[v].begin(), cur + abs(a[i] - a[v]));
		};
		trans(lef[i][j]);
		trans(rig[i][j]);
	}
	
	return f[enn][0] == linf? -1: f[enn][0];
}