#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
map<pair<int,int>,vector<pair<int,int>>> ma;
map<int,vector<int>> at;
map<pair<int,int>,bool> vis;
map<int,vector<int>> add_at;
map<int,vector<int>> rem_at;
map<int,int> prev1;
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)
{
set<int> sp(begin(h),end(h));
int n=x.size();
int m=l.size();
// if(sp.size()==1)
// {
for(int i=0;i<n;i++)
{
at[i].push_back(0);
at[i].push_back(h[i]);
}
for(int i=0;i<m;i++)
{
add_at[l[i]].push_back(y[i]);
rem_at[r[i]+1].push_back(y[i]);
prev1[y[i]]=-1;
}
set<int> cur;
for(int i=0;i<n;i++)
{
for(auto j:rem_at[i])
{
prev1[j]=-1;
cur.erase(j);
}
for(auto j:add_at[i])
{
cur.insert(j);
}
auto it=begin(cur);
while(it!=end(cur) and (*it)<=h[i])
{
at[i].push_back(*it);
if(prev1[*it]!=-1)
{
// cout<<"There is a edge "<<x[prev1[*it]]<<' '<<*it<<' '<<x[i]<<' '<<*it<<endl;
ma[{x[prev1[*it]],*it}].push_back({x[i],*it});
ma[{x[i],*it}].push_back({x[prev1[*it]],*it});
}
prev1[*it]=i;
it++;
}
}
for(int i=0;i<n;i++)
{
sort(begin(at[i]),end(at[i]));
// cout<<"For "<<i<<endl;;
// for(auto j:at[i])
// {
// cout<<j<<' ';
// }
// cout<<endl;
for(int j=1;j<at[i].size();j++)
{
ma[{x[i],at[i][j]}].push_back({x[i],at[i][j-1]});
ma[{x[i],at[i][j-1]}].push_back({x[i],at[i][j]});
}
}
set<vector<long long>> di;
di.insert({0,x[s],0});
while(di.size())
{
auto fi=*begin(di);
di.erase(begin(di));
if(vis[{fi[1],fi[2]}])
continue;
// cout<<"I am "<<fi[0]<<' '<<fi[1]<<' '<<fi[2]<<endl;
if(fi[1]==x[g] and fi[2]==0)
{
return fi[0];
}
vis[{fi[1],fi[2]}]=1;
for(auto [nx,ny]:ma[{fi[1],fi[2]}])
{
// cout<<"From "<<fi[1]<<' '<<fi[2]<<" can go to "<<nx<<' '<<ny<<endl;
di.insert({fi[0]+abs(nx-fi[1])+abs(fi[2]-ny),nx,ny});
}
}
return -1;
// }
// if(n<=50 and m<=50)
{
for(int i=0;i<n;i++)
{
at[i].push_back(0);
at[i].push_back(h[i]);
}
for(int j=0;j<m;j++)
{
int sb=l[j];
int eb=r[j];
int prev=-1;
for(;sb<=eb;sb++)
{
if(h[sb]>=y[j])
{
at[sb].push_back(y[j]);
if(prev!=-1)
{
ma[{x[prev],y[j]}].push_back({x[sb],y[j]});
ma[{x[sb],y[j]}].push_back({x[prev],y[j]});
}
prev=sb;
}
}
}
for(int i=0;i<n;i++)
{
sort(begin(at[i]),end(at[i]));
for(int j=1;j<at[i].size();j++)
{
ma[{x[i],at[i][j]}].push_back({x[i],at[i][j-1]});
ma[{x[i],at[i][j-1]}].push_back({x[i],at[i][j]});
}
}
set<vector<long long>> di;
di.insert({0,x[s],0});
while(di.size())
{
auto fi=*begin(di);
di.erase(begin(di));
if(vis[{fi[1],fi[2]}])
continue;
// cout<<"I am "<<fi[0]<<' '<<fi[1]<<' '<<fi[2]<<endl;
if(fi[1]==x[g] and fi[2]==0)
{
return fi[0];
}
vis[{fi[1],fi[2]}]=1;
for(auto [nx,ny]:ma[{fi[1],fi[2]}])
{
// cout<<"From "<<fi[1]<<' '<<fi[2]<<" can go to "<<nx<<' '<<ny<<endl;
di.insert({fi[0]+abs(nx-fi[1])+abs(fi[2]-ny),nx,ny});
}
}
}
return -1;
}
