import java.util.*;
class walk {
int n;
int m;
int count;
ArrayList<int[]>[] adj;
public long min_distance(int[] x, int[] h, int[] l, int[] r, int[] y, int s, int g) {
n = x.length;
m = l.length;
TreeSet<Building> buildings = new TreeSet<Building>();
for (int i = 0; i < n; i++) {
Building building = new Building(i, x[i], h[i]);
buildings.add(building);
}
count = n;
adj = new ArrayList[2000000];
for (int i = 0; i < adj.length; i++) adj[i] = new ArrayList<int[]>();
int[][] buildingHeights = new int[n][2];
int[][] walkHeights = new int[m][2];
for (int i = 0; i < n; i++) {
buildingHeights[i][0] = i;
buildingHeights[i][1] = h[i];
}
for (int i = 0; i < m; i++) {
walkHeights[i][0] = i;
walkHeights[i][1] = y[i];
}
Arrays.sort(buildingHeights, new ArrayComparator());
Arrays.sort(walkHeights, new ArrayComparator());
int currentWalk = 0;
int currentBuilding = 0;
int[][] coords = new int[adj.length][2];
while (currentWalk < m) {
while (buildingHeights[currentBuilding][1] < walkHeights[currentWalk][1]) {
int index = buildingHeights[currentBuilding][0];
buildings.remove(new Building(index, x[index], h[index]));
currentBuilding++;
}
int walkIndex = walkHeights[currentWalk][0];
Set<Building> tailSet = buildings.tailSet(new Building(-1, x[l[walkIndex]], y[walkIndex]), true);
int prevX = -1;
for (Building b : tailSet) {
int[] coord = {b.x, walkHeights[currentWalk][1]};
coords[count] = coord;
if (b.x > x[r[walkIndex]]) break;
for (int[] adjacent : adj[b.index]) {
int dist2 = adjacent[1];
int[] ar1 = {adjacent[0], Math.abs(dist2 - y[walkIndex])};
int[] ar2 = {count, Math.abs(dist2 - y[walkIndex])};
adj[count].add(ar1);
adj[adjacent[0]].add(ar2);
}
int[] ar1 = {b.index, y[walkIndex]};
int[] ar2 = {count, y[walkIndex]};
adj[count].add(ar1);
adj[b.index].add(ar2);
if (b.x != x[l[walkIndex]]) {
int dist = x[b.index] - prevX;
int[] ar3 = {count, dist};
int[] ar4 = {count - 1, dist};
adj[count - 1].add(ar3);
adj[count].add(ar4);
}
count++;
prevX = b.x;
}
currentWalk++;
}
long[] shortestDistance = new long[adj.length];
Arrays.fill(shortestDistance, Long.MAX_VALUE);
PriorityQueue<long[]> pq = new PriorityQueue<long[]>(new ArrayComparator2());
long[] ar1 = {s, 0};
pq.add(ar1);
while (!pq.isEmpty()) {
long[] node = pq.remove();
int index = (int) node[0];
//System.out.println(node[0] + " " + adj[index].size());
if (node[1] >= shortestDistance[index]) continue;
shortestDistance[index] = node[1];
for (int[] adjacent : adj[index]) {
if (shortestDistance[adjacent[0]] == Long.MAX_VALUE) {
long[] ar = {adjacent[0], adjacent[1] + shortestDistance[index]};
pq.add(ar);
}
}
}
return shortestDistance[g];
}
private static class ArrayComparator implements Comparator<int[]> {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[1], o2[1]);
}
}
private static class ArrayComparator2 implements Comparator<long[]> {
@Override
public int compare(long[] o1, long[] o2) {
return Long.compare(o1[1], o2[1]);
}
}
private static class Building implements Comparable<Building> {
int index;
int x;
int h;
public Building(int index, int x, int h) {
this.index = index;
this.x = x;
this.h = h;
}
@Override
public int compareTo(Building o) {
int compare1 = Integer.compare(x, o.x);
if (compare1 != 0) return compare1;
return Integer.compare(h, o.h);
}
}
}
