#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int n;
vector<int32_t> h;
vector<pair<int,int>> aint[400005];
void build(int nod, int st, int dr)
{
for(int i=st;i<=dr;i++)
aint[nod].push_back({h[i],i});
sort(aint[nod].begin(),aint[nod].end());
reverse(aint[nod].begin(),aint[nod].end());
if(st==dr)
return;
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
}
pair<int,int> qry(int nod, int st, int dr, int le, int ri, int lim)
{
if(le>ri)
return {-1,-1};
if(le==st && dr==ri)
{
return aint[nod][0];
}
int mij=(st+dr)/2;
return max(qry(nod*2,st,mij,le,min(mij,ri),lim), qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,lim));
}
vector<int> incep[100005],termina[100005];
set<pair<int,int>> s;
map<int,int> cnt;
void baga(int x)
{
auto it = s.lower_bound({x,0});
if((*it).first == x)
return;
int mnm=INF;
if(it != s.end())
mnm = min(mnm, (*it).second + abs((*it).first - x));
if(it != s.begin())
{
it--;
mnm = min(mnm, (*it).second + abs((*it).first - x));
}
s.insert({x,mnm});
}
long long min_distance(vector<int32_t> x, vector<int32_t> coph, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t src, int32_t g)
{
h = coph;
n = h.size();
build(1,0,n-1);
for(int i=0;i<l.size();i++)
{
pair<int,int> x = qry(1,0,n-1,l[i]+1,r[i]-1,y[i]);
if(x.first > max(h[l[i]], h[r[i]]) && 0)
{
//assert(0);
incep[l[i]].push_back(y[i]);
termina[x.second].push_back(y[i]);
incep[x.second].push_back(y[i]);
termina[r[i]].push_back(y[i]);
}
else
{
incep[l[i]].push_back(y[i]);
termina[r[i]].push_back(y[i]);
}
}
assert(n!=1);
s.insert({0,0});
cnt[0]++;
termina[0].push_back(0);
incep[n-1].push_back(0);
for(int i=0;i<n;i++)
{
for(int x:incep[i])
{
cnt[x]++;
baga(x);
}
for(int x:termina[i])
{
auto it = s.lower_bound({x,0});
assert(it != s.end() && (*it).first == x);
cnt[x]--;
if(cnt[x]==0)
s.erase(it);
}
}
assert(!s.empty());
auto cop = *s.begin();
if(cop.second == INF)
return -1;
return cop.second + x[n-1] - x[0];
}
