#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>l,r,y,x,h;
const int base = 1<<17;
int drzewo[2*base];
int wiekszeL(int x, int val){
x+=base;
while(drzewo[x]<val && x&(x-1)){
if(x%2==1)x/=2;
else x--;
}
if(drzewo[x]>=val){
while(x<base)
if(drzewo[x*2+1]>=val)
x=x*2+1;
else
x=x*2;
return x-base;
}
else
return -1;
}
int wiekszeR(int x, int val){
x+=base;
while(drzewo[x]<val && x&(x+1)){
if(x%2==0)x/=2;
else x++;
}
if(drzewo[x]>=val){
while(x<base)
if(drzewo[x*2]>=val)
x=x*2;
else
x=x*2+1;
return x-base;
}
else
return base;
}
int tree[2*base];
void ustaw(int w, int l, int p, int a, int b, int v){
if(a<=l && p<=b){
tree[w] = v;
return;
}
if(b<l || p<a)return;
if(tree[w]!=-1)
tree[w*2] = tree[w*2+1] = tree[w];
ustaw(w*2, l, (l+p)/2, a, b, v);
ustaw(w*2+1, (l+p)/2+1, p, a, b, v);
tree[w] = -1;
}
int odczyt(int w){
int res = -1;
w+=base;
while(w>0){
if(tree[w]!=-1)
res = tree[w];
w/=2;
}
return res;
}
void dodaj(int a, int b, int h){
l.push_back(a);
r.push_back(b);
y.push_back(h);
}
vector<pair<int,long long>>graf[700010];
long long dist[700010];
bool odw[700010];
map<pair<int,int>,int>mapa;
long long odl(pair<int,int>a, pair<int,int>b){
return abs(a.second-b.second);
}
long long odl1(pair<int,int>a, pair<int,int>b){
return abs(x[a.first]-x[b.first]);
}
map<int,vector<pair<int,int>>>poziomy;
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int s, int g) {
x = X;
h = H;
// podzielic kazda pozioma
// dla kazdej poziomej wyznaczyc pozioma w dol z obu koncy
vector<tuple<int,int,int,int>>przedzialy;
int n = x.size();
int m = L.size();
int i;
for(i=0;i<n;i++)
drzewo[i+base]=h[i];
for(i=base-1;i>0;i--)
drzewo[i]=max(drzewo[i*2], drzewo[i*2+1]);
if(s>g)swap(s,g);
for(i=0;i<m;i++){
poziomy[Y[i]].push_back({L[i],R[i]});
if(L[i]<s && R[i]>g){
dodaj(L[i],s,Y[i]);
dodaj(s,g,Y[i]);
dodaj(g,R[i],Y[i]);
}
else if(L[i]<s && R[i]>s){
dodaj(L[i],s,Y[i]);
dodaj(s,R[i],Y[i]);
}
else if(g<R[i] && L[i]<g){
dodaj(L[i],g,Y[i]);
dodaj(g,R[i],Y[i]);
}
else{
dodaj(L[i],R[i],Y[i]);
}
}
m = l.size();
for(i=0;i<m;i++)
przedzialy.push_back({y[i],l[i],r[i],0});
sort(przedzialy.begin(), przedzialy.end());
for(i=0;i<m;i++)
get<3>(przedzialy[i]) = i;
for(i=0;i<n;i++)tree[i+base] = -1;
for(i=base-1;i>0;i--)
tree[i] = -1;
ustaw(1, 0,base-1,s,s,0);
ustaw(1, 0,base-1,g,g,0);
mapa[{s,0}]=0;
mapa[{g,0}]=1;
for(auto j: przedzialy){
auto [Y,L,R,i] = j;
int a = wiekszeR(L, Y);
if(a<=R){
int b = odczyt(a);
if(b!=-1 && mapa.find({a, b})==mapa.end())
mapa[{a,b}] = mapa.size();
if(mapa.find({a, Y})==mapa.end())
mapa[{a,Y}] = mapa.size();
}
a = wiekszeL(R,Y);
if(a>=L){
int b = odczyt(a);
if(b!=-1 &&mapa.find({a, b})==mapa.end())
mapa[{a,b}] = mapa.size();
if(mapa.find({a, Y})==mapa.end())
mapa[{a,Y}] = mapa.size();
}
ustaw(1, 0, base-1, L, R, Y);
}
vector<pair<pair<int,int>,int>>wartosci;
for(auto j=mapa.begin();j!=mapa.end();j++){
auto xd = *j;
wartosci.push_back({xd.first, xd.second});
auto next = j;
next++;
if(next==mapa.end())break;
if((*next).first.first==(*j).first.first){
graf[(*next).second].push_back({(*j).second, odl((*j).first, (*next).first)});
graf[(*j).second].push_back({(*next).second, odl((*j).first, (*next).first)});
}
}
for(auto &j: poziomy){
auto &vec = j.second;
vector<pair<int,int>>dobre;
sort(vec.begin(), vec.end());
int koniec = (*vec.begin()).second, pocz = (*vec.begin()).first;
for(auto k: vec){
if(k.first<=koniec)
koniec = max(k.second, koniec);
else{
dobre.push_back({pocz, koniec});
pocz = k.first;
koniec = k.second;
}
}
dobre.push_back({pocz,koniec});
vec = dobre;
}
mapa.clear();
for(auto j:wartosci)
mapa[{j.first.second,j.first.first}]=j.second;
for(auto j=mapa.begin();j!=mapa.end();j++){
if((*j).first.first==0)continue;
auto next = j;
next++;
if(next==mapa.end())break;
if((*next).first.first==(*j).first.first){
int a =(*j).first.second, b = (*next).first.second;
auto &pom = poziomy[(*j).first.first];
if(upper_bound(pom.begin(), pom.end(), make_pair(a,1000000000))==upper_bound(pom.begin(), pom.end(), make_pair(b,1000000000))){
graf[(*next).second].push_back({(*j).second, x[(*next).first.second]-x[(*j).first.second]});
graf[(*j).second].push_back({(*next).second, x[(*next).first.second]-x[(*j).first.second]});
}
}
}
priority_queue<pair<long long, int>>kolejka;
dist[0] = 1;
kolejka.push({-1,0});
while(kolejka.size()){
auto a = kolejka.top();
kolejka.pop();
if(odw[a.second])continue;
odw[a.second]=1;
for(auto j: graf[a.second]){
if(dist[j.first]==0 || dist[j.first]>dist[a.second]+j.second){
dist[j.first]=dist[a.second]+j.second;
kolejka.push({-dist[j.first], j.first});
}
}
}
return dist[1]-1;
}
