#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
set<int> there[nmax];
map<int,int> id[nmax];
set<int> noted[nmax];
vector<long long> dist;
vector< vector< pair<int,int> > > adj;
vector<int> inp;
void add_edge(int x1,int y1,int x2,int y2)
{
int p=id[x1][y1];
int q=id[x2][y2];
int d=abs(inp[x1]-inp[x2])+abs(y1-y2);
//cout<<"x1= "<<x1<<" y1= "<<y1<<" x2= "<<x2<<" y2= "<<y2<<" d= "<<d<<" p= "<<p<<" q= "<<q<<endl;
while(adj.size()<=p)adj.push_back({});
while(adj.size()<=q)adj.push_back({});
adj[p].push_back({q,d});
adj[q].push_back({p,d});
}
priority_queue< pair<long long,int> > pq;
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
inp=x;
for(int i=0;i<x.size();i++)
there[i].insert(0);
for(int i=0;i<y.size();i++)
{
//cout<<"line: "<<l[i]<<" "<<r[i]<<" "<<y[i]<<endl;
for(int j=l[i];j<=r[i];j++)
if(h[j]>=y[i])
{
//cout<<"push "<<j<<" h= "<<y[i]<<endl;
there[j].insert(y[i]);
noted[i].insert(j);
}
}
int pointer=0;
for(int i=0;i<x.size();i++)
{
for(auto w:there[i])
{
id[i][w]=pointer;
//cout<<"id "<<i<<" "<<w<<" -> "<<pointer<<endl;
pointer++;
}
}
//cout<<"towers: "<<endl;
for(int i=0;i<x.size();i++)
{
int prv=0;
for(auto w:there[i])
{
if(w)
{
add_edge(i,prv,i,w);
}
prv=w;
}
}
//cout<<"---"<<endl;
for(int i=0;i<y.size();i++)
{
//cout<<"i= "<<i<<"---"<<endl;
int prv=-1;
for(auto w:noted[i])
{
if(prv!=-1)
{
add_edge(prv,y[i],w,y[i]);
}
prv=w;
}
}
/*
cout<<"there: "<<endl;
for(int i=0;i<x.size();i++)
{
cout<<i<<" -> ";for(auto j:there[i])cout<<j<<" ";cout<<endl;
}
*/
for(int i=0;i<=pointer;i++)
dist.push_back(-1);
pq.push({0,id[s][0]});
while(pq.size())
{
pair<long long,int> tp=pq.top();
pq.pop();
tp.first=-tp.first;
if(dist[tp.second]!=-1)continue;
dist[tp.second]=tp.first;
//cout<<"dist: "<<tp.second<<" -> "<<tp.first<<endl;
for(auto w:adj[tp.second])
pq.push({-(tp.first+w.second),w.first});
}
return dist[id[g][0]];
}
/*
int main() {
int n, m;
assert(2 == scanf("%d%d", &n, &m));
vector<int> x(n), h(n);
for (int i = 0; i < n; i++)
assert(2 == scanf("%d%d", &x[i], &h[i]));
vector<int> l(m), r(m), y(m);
for (int i = 0; i < m; i++)
assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
int s, g;
assert(2 == scanf("%d%d", &s, &g));
fclose(stdin);
long long result = min_distance(x, h, l, r, y, s, g);
printf("%lld\n", result);
fclose(stdout);
return 0;
}
*/
