import java.math.*;
import java.util.*;
class walk {
class Pair implements Comparator <Pair> {
int first, second;
Pair () {}
Pair (int first, int second) {
this.first = first; this.second = second;
}
public int compare(Pair a, Pair b) {
if(a.first == b.first) return a.second - b.second;
return a.first - b.first;
}
}
class Node implements Comparator <Node> {
long dist;
int pos, line;
Node () {}
Node (long dist, int pos, int line) {
this.dist = dist; this.pos = pos; this.line = line;
}
public int compare(Node a, Node b) {
if(a.dist != b.dist) return Long.compare(a.dist, b.dist);
if(a.pos != b.pos) return a.pos - b.pos;
return a.line - b.line;
}
}
public long min_distance(int[] x, int[] h, int[] l, int[] r, int[] y, int f, int g) {
int n = x.length;
int m = y.length;
TreeSet <Pair> [] s = new TreeSet [n];
ArrayList <Pair> ls = new ArrayList <> ();
TreeSet <Integer> [] ch = new TreeSet [m];
for(int i = 0; i < n; i++) {
s[i] = new TreeSet <> (new Pair());
ls.add(new Pair(-h[i], -i - 1));
}
for(int i = 0; i < m; i++) {
ls.add(new Pair(-y[i], i));
}
Collections.sort(ls, new Pair());
TreeSet <Integer> aux = new TreeSet <> ();
for(Pair i : ls) {
if(i.second < 0) {
aux.add(-i.second - 1);
} else {
ch[i.second] = new TreeSet <>
(aux.subSet(l[i.second], r[i.second] + 1));
for(int j : ch[i.second]) {
s[j].add(new Pair(-i.first, i.second));
}
}
}
s[f].add(new Pair(0, m));
s[g].add(new Pair(0, m + 1));
TreeMap <Pair, Long> dist = new TreeMap <> (new Pair());
TreeSet <Node> q = new TreeSet <> (new Node());
q.add(new Node(0L, f, m));
dist.put(new Pair(f, m), 0L);
while(!q.isEmpty()) {
int pos = q.first().pos;
int line = q.first().line;
long current = q.first().dist;
q.remove(new Node(current, pos, line));
int high = (line >= m) ? 0 : y[line];
if(dist.get(new Pair(pos, line)) != current) continue;
ArrayList <Pair> can = new ArrayList <> ();
if(line < m) {
Integer a = ch[line].lower(pos);
Integer b = ch[line].higher(pos);
if(a != null) can.add(new Pair(a, line));
if(b != null) can.add(new Pair(b, line));
}
Pair a = s[pos].lower(new Pair(high, line));
Pair b = s[pos].higher(new Pair(high, line));
if(a != null) {
can.add(new Pair(pos, a.second));
}
if(b != null) {
can.add(new Pair(pos, b.second));
}
for(Pair i : can) {
int nxtH = (i.second >= m) ? 0 : y[i.second];
long d = current + Math.abs(x[pos] - x[i.first]) +
Math.abs(high - nxtH);
if(dist.get(i) == null || dist.get(i) > d) {
dist.put(new Pair(i.first, i.second), d);
q.add(new Node(d, i.first, i.second));
}
}
}
return dist.get(new Pair(g, m + 1)) == null ? -1 : dist.get(new Pair(g, m + 1));
}
}
