#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
set<int> there[nmax];
map<int,int> id[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;
int tree[4*nmax];
vector<int> mem_h,mem_l,mem_r,mem_y;
void build(int node,int l,int r)
{
if(l==r)
{
tree[node]=mem_h[l];
return;
}
int av=(l+r)/2;
build(node*2,l,av);
build(node*2+1,av+1,r);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
void push(int i,int j)
{
//cout<<"push "<<i<<" "<<j<<endl;
if(mem_l[i]<=j&&j<=mem_r[i])
{
if(mem_h[j]>=mem_y[i])
{
//cout<<"in"<<endl;
there[j].insert(mem_y[i]);
}
}
}
int query(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)return tree[node];
int av=(l+r)/2;
int ret=0;
if(lq<=av)ret=max(ret,query(node*2,l,av,lq,min(av,rq)));
if(av<rq)ret=max(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));
return ret;
}
int get_first(int l,int r,int h)
{
if(l>r)return -1;
if(query(1,0,mem_h.size()-1,l,r)<h)return -1;
int ok=r,not_ok=l-1;
while(ok-not_ok>1)
{
int av=(ok+not_ok)/2;
if(query(1,0,mem_h.size()-1,l,av)<h)not_ok=av;
else ok=av;
}
return ok;
}
int get_last(int l,int r,int h)
{
if(l>r)return -1;
if(query(1,0,mem_h.size()-1,l,r)<h)return -1;
int ok=l,not_ok=r+1;
while(not_ok-ok>1)
{
int av=(ok+not_ok)/2;
if(query(1,0,mem_h.size()-1,av,r)<h)not_ok=av;
else ok=av;
}
return ok;
}
vector< pair<int,int> > updates[nmax];
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) {
mem_l=l;
mem_r=r;
mem_y=y;
if(s>g)swap(s,g);
inp=x;
mem_h=h;
build(1,0,h.size()-1);
for(int i=0;i<x.size();i++)
there[i].insert(0);
for(int i=0;i<y.size();i++)
{
updates[l[i]].push_back({y[i],1});
updates[r[i]+1].push_back({y[i],-1});
//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);
}
*/
push(i,l[i]);
push(i,get_last(0,l[i]-1,y[i]));
push(i,s);
push(i,get_first(s+1,g-1,y[i]));
push(i,get_last(s+1,g-1,y[i]));
push(i,g);
push(i,get_first(g+1,r[i],y[i]));
push(i,r[i]);
}
set<int> active={};
map<int,int> cnt_active={};
for(int i=0;i<x.size();i++)
{
for(auto w:updates[i])
{
cnt_active[w.first]+=w.second;
active.erase(w.first);
if(cnt_active[w.first])active.insert(w.first);
}
set<int> help=there[i];
for(auto w:help)
{
set<int>::iterator it=active.lower_bound(w);
if(it!=active.begin())
{
it--;
int val=*it;
if(0<=val&&val<=h[i])there[i].insert(val);
//cout<<"low "<<*it<<endl;
}
it=active.upper_bound(w);
if(it!=active.end())
{
int val=*it;
if(0<=val&&val<=h[i])there[i].insert(val);
//cout<<"high "<<*it<<endl;
}
}
}
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++)
{
cout<<"i= "<<i<<" : ";
for(auto w:there[i])
cout<<w<<" ";
cout<<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;
map<int, vector<int> > seen_by_y={};
for(int i=0;i<x.size();i++)
{
for(auto w:there[i])
seen_by_y[w].push_back(i);
}
for(int i=0;i<y.size();i++)
{
//cout<<l[i]<<" "<<r[i]<<" "<<y[i]<<" :"<<endl;
vector<int> me=seen_by_y[y[i]];
int prv=-1;
for(auto w:me)
if(l[i]<=w&&w<=r[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;
}
*/
