#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
const int NN = 1<<20;
int tab[NN], hei[NN];
int drz[2 * N], drz2[2 * N], drz3[2 * N];
int cnt = 0;
pair<int, int> co[NN];
vector<pair<int, ll>> ed[NN];
ll dis[NN];
pair<pair<int, int>, int> wal[NN];
bool vis[NN];
vector<int> poi[NN];
vector<int> sky[NN];
void Sett(int a, int b, int x)
{
a += N - 1; b += N + 1;
while(a / 2 != b / 2)
{
if(a % 2 == 0) drz3[a + 1] = x;
if(b % 2 == 1) drz3[b - 1] = x;
a /= 2;
b /= 2;
}
}
int Ma(int v)
{
v += N;
int ans = drz3[v];
while(v > 0)
{ans = max(ans, drz3[v]); v /= 2;}
return ans;
}
void DoDrz(int n)
{
for(int i = 1; i <= n; ++i)
drz[i + N] = hei[i];
for(int i = 1; i <= n; ++i)
drz2[i + N] = 1;
for(int i = N - 1; i >= 1; --i)
drz[i] = max(drz[i * 2], drz[i * 2 + 1]);
for(int i = N - 1; i >= 1; --i)
drz2[i] = drz2[i * 2] + drz2[i * 2 + 1];
}
int Find(int a, int b, int x, int r)
{
a += N - 1; b += N + 1;
int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
while(a / 2 != b / 2)
{
if(a % 2 == 0 && drz[a + 1] >= x)
{
if(a1 == 0)
a1 = a + 1;
a2 = a + 1;
}
if(b % 2 == 1 && drz[b - 1] >= x)
{
if(b1 == 0)
b1 = b - 1;
b2 = b - 1;
}
a /= 2; b /= 2;
}
if(r == 0)
a = a1;
if(a == 0)
a = b2;
if(r == 1)
a = b1;
if(a == 0)
a = a2;
while(a < N)
{
a = a * 2 + r;
if(drz[a] < x) a ^= 1;
}
return a - N;
}
bool C(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
{
return (make_pair(a.nd, a.st) < make_pair(b.nd, b.st));
}
void Clr(int v, int a, int b, int pz, int kz, int id)
{
if(drz2[v] <= 0 || a > kz || b < pz) return;
if(v >= N)
{
v -= N;
//cerr << "clr: " << v << " " << id << "\n";
if(hei[v] >= wal[id].nd)
sky[v].pb(id);
--drz2[v + N];
return;
}
Clr(v * 2, a, (a + b) / 2, pz, kz, id);
Clr(v * 2 + 1, (a + b) / 2 + 1, b, pz, kz, id);
drz2[v] = drz2[v * 2] + drz2[v * 2 + 1];
}
inline ll D(int i, int j)
{
ll d1 = max(co[i].st - co[j].st, co[j].st - co[i].st);
ll d2 = max(co[i].nd - co[j].nd, co[j].nd - co[i].nd);
return d1 + d2;
}
inline void A(int x, int y)
{
ll d = D(x, y);
ed[x].pb(make_pair(y, d)); ed[y].pb(make_pair(x, d));
}
set<pair<int, int>> inter;
set<pair<int, int>>::iterator it;
bool IT(pair<int, int> a, pair<int, int> b)
{
return (max(a.st, b.st) <= min(a.nd, b.nd));
}
pair<int, int> DI(pair<int, int> a, pair<int, int> b)
{
return make_pair(min(a.st, b.st), max(a.nd, b.nd));
}
void Add(pair<int, int> a)
{
it = inter.lower_bound(a);
if(it != inter.end() && IT(*it, a))
{
a = DI(a, *it); inter.erase(it);
}
it = inter.lower_bound(a);
if(it != inter.begin())
{
--it;
if(IT(*it, a))
{
a = DI(a, *it); inter.erase(it);
}
}
inter.insert(a);
}
void Do(int &k)
{
vector<pair<pair<int, int>, int>> nxt;
for(int i = 1; i <= k; ++i)
{
Add(wal[i].st);
//cerr << "xd " << i << "\n";
if(i == k || wal[i].nd != wal[i + 1].nd)
{
for(it = inter.begin(); it != inter.end(); ++it)
nxt.pb(make_pair(*it, wal[i].nd));
inter.clear();
}
}
k = nxt.size();
for(int i = 1; i <= k; ++i)
wal[i] = nxt[i - 1];
}
void SanInput(int n, int &k, int u, int v)
{
int dod = 0;
sort(wal + 1, wal + 1 + k, C);
Do(k);
for(int i = 1; i <= k; ++i)
{
//cerr << "skypath: " << i << " " << wal[i].st.st << " " << wal[i].st.nd << " " << wal[i].nd << "\n";
vector<int> cur = {wal[i].st.st, wal[i].st.nd}, hl;
if(wal[i].st.st < u && wal[i].st.nd > u)
{
int v1 = Find(1, u, wal[i].nd, 1), v2 = Find(u, n, wal[i].nd, 0);
cur.pb(v1); cur.pb(v2);
}
if(wal[i].st.st < v && wal[i].st.nd > v)
{
int v1 = Find(1, v, wal[i].nd, 1), v2 = Find(v, n, wal[i].nd, 0);
cur.pb(v1); cur.pb(v2);
}
sort(cur.begin(), cur.end());
for(int j = 0; j < (int)cur.size(); ++j)
if(j == 0 || cur[j] != cur[j - 1]) hl.pb(cur[j]);
cur = hl;
wal[i].st.nd = cur[1];
for(int j = 1; j < (int)cur.size() - 1; ++j)
{
++dod;
wal[k + dod] = make_pair(make_pair(cur[j], cur[j + 1]), wal[i].nd);
}
}
k += dod;
sort(wal + 1, wal + 1 + k, C);
for(int i = 1; i <= k; ++i)
{
Clr(1, 0, N - 1, wal[i].st.st, wal[i].st.nd, i);
int a1 = Ma(wal[i].st.st), a2 = Ma(wal[i].st.nd);
sky[wal[i].st.st].pb(i);
if(a1 != 0)
sky[wal[i].st.st].pb(a1);
sky[wal[i].st.nd].pb(i);
if(a2 != 0)
sky[wal[i].st.nd].pb(a2);
Sett(wal[i].st.st, wal[i].st.nd, i);
}
cnt = n;
for(int i = 1; i <= n; ++i)
{
vector<int> hlp;
sort(sky[i].begin(), sky[i].end());
for(int j = 0; j < (int)sky[i].size(); ++j)
if(j == 0 || sky[i][j] != sky[i][j - 1]) hlp.pb(sky[i][j]);
sky[i] = hlp;
co[i] = make_pair(tab[i], 0);
int pr = i;
//cerr << "Sky: " << i << " " << "\n";
for(int j = 0; j < (int)sky[i].size(); ++j)
{
if(j != 0) pr = cnt;
if(j == 0 || wal[sky[i][j]].nd != wal[sky[i][j - 1]].nd)
{++cnt; co[cnt] = make_pair(tab[i], wal[sky[i][j]].nd); A(cnt, pr);}
poi[sky[i][j]].pb(cnt);
//cerr << sky[i][j] << " ";
}
//cerr << "\n";
}
for(int i = 1; i <= k; ++i)
for(int j = 1; j < (int)poi[i].size(); ++j)
A(poi[i][j - 1], poi[i][j]);
}
void Dijkstra(int s)
{
int n = cnt;
priority_queue<pair<ll, int>> q;
for(int i = 1; i <= n; ++i) dis[i] = I;
dis[s] = 0LL;
q.push(make_pair(0LL, s));
while((int)q.size() > 0)
{
int v = q.top().nd; q.pop();
if(vis[v]) continue;
vis[v] = true;
//cerr << "Dijkstra: " << v << " " << co[v].st << " " << co[v].nd << " " << dis[v] << "\n";
for(int i = 0; i < (int)ed[v].size(); ++i)
{
//cout << "ed: " << ed[v][i].st << " " << ed[v][i].nd << "\n";
ll d = dis[v] + ed[v][i].nd;
if(d < dis[ed[v][i].st])
{
dis[ed[v][i].st] = d;
q.push(make_pair(-d, ed[v][i].st));
}
}
}
}
long long min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g)
{
int u = _s + 1, v = _g + 1;
int n = _x.size(), k = _l.size();
for(int i = 1; i <= n; ++i)
{tab[i] = _x[i - 1]; hei[i] = _h[i - 1]; ++cnt;}
for(int i = 1; i <= k; ++i)
wal[i] = make_pair(make_pair(_l[i - 1] + 1, _r[i - 1] + 1), _y[i - 1]);
DoDrz(n);
SanInput(n, k, u, v);
Dijkstra(u);
if(dis[v] == I) return -1;
return dis[v];
}
