Fix $i.$ Consider a graph of time versus $y$-coordinate; then world $i$ is represented by a line of slope $-i$. Call a point $(T,Y)$ on this graph "attainable" if it is possible for cow $i$ to be at $y$-coordinate $Y$ at time $T.$

Subtask 1: $O(N^3)$ BFS

Subtask 2: It can be shown that the shortest path between any two worlds contains at most one intermediate world. So for each query, iterate over all worlds aside from the start and the end and check if it can be the intermediate one in $O(N^2)$ time. Alternatively, speed up the solution from subtask 1 with bitset.

Subtask 3: WLOG suppose that $A[Q_i]<A_i.$ Clearly no attainable points lie below the lower convex hull of all lines representing worlds $j$ such that $A_j\ge A_i$. Furthermore, all points on this hull are attainable. Thus, it suffices to find the $t$-coordinate of the intersection of the line $y=-Q_it+A[Q_i]$ with this lower hull. We can compute the hulls for all $i$ by sorting the lines by $A_i$ in decreasing order and adding them to the hull one by one. This can be done using a deque. After computing the hull for $i,$ we can binary search to find the intersection of the line with the hull.

Spencer's Code:

import java.io.*;
import java.util.*;

public class falling {
	public static class Obj implements Comparable<Obj>{
		public long y, d;
		public int ind;
		public Obj(long a, long b, int c) {
			y = a;
			d = b;
			ind = c;
		}
		public int compareTo(Obj o) {
			return Long.compare(y, o.y);
		}
	}
	public static long gc(long a, long b) {
		if(a==0L || b==0L) {
			return a+b;
		}
		return gc(b%a,a);
	}
	public static class Pair{
		public long first, second;
		Pair(long a, long b){
			first = a;
			second = b;
		}
	}
	public static Pair make_pair(long a, long b) {
		return new Pair(a,b);
	}
	public static Pair ev(Obj a, Obj b) {
		return make_pair(Math.abs(a.y-b.y),Math.abs(a.d-b.d));
	}
	public static int cmp(Obj a, Obj b, Obj c) {
		Pair l = ev(a,c);
		Pair r = ev(b,c);
		long res = l.first*r.second-r.first*l.second;
		if(res<0L) {
			return -1;
		}
		if(res==0L) {
			return 0;
		}
		return 1;
	}
	public static boolean used(Obj a, Obj b, Obj c) {
		Pair l = ev(a,b);
		Pair r = ev(b,c);
		long res = l.first*r.second-r.first*l.second;
		return (res<0L);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new FileReader("falling.in"));
		int n = Integer.parseInt(in.readLine());
		String[] line = in.readLine().split(" ");
		long[] a = new long[n];
		int[] q = new int[n];
		long[] num = new long[n];
		long[] dem = new long[n];
		for(int i = 0; i<line.length; i++) {
			a[i] = Integer.parseInt(line[i]);
		}
		line = in.readLine().split(" ");
		for(int i =0 ; i<line.length; i++) {
			q[i] = Integer.parseInt(line[i])-1;
		}
		ArrayList<Obj> li = new ArrayList<Obj>();
		ArrayList<Obj> all = new ArrayList<Obj>();
		for(int i = 0; i<n; i++) {
			li.add(new Obj(a[i],-(i+1),i));
			all.add(new Obj(a[i],-(i+1),i));
		}
		Collections.sort(li);
		ArrayList<Obj> cur = new ArrayList<Obj>();
		for(int i = li.size()-1; i>=0; i--) {
			Obj now = li.get(i);
			while(cur.size()>0) {
				if(now.d < cur.get(cur.size()-1).d) {
					cur.remove(cur.size()-1);
					continue;
				}
				if(cur.size()>1 && !used(now,cur.get(cur.size()-1),cur.get(cur.size()-2))) {
					cur.remove(cur.size()-1);
					continue;
				}
				break;
			}
			cur.add(now);
			int ind = li.get(i).ind;
			if(a[ind]>a[(int)q[(int)ind]]) {
				if(cur.get(0).d > -(q[ind]+1)) {
					num[ind]=-1;
				}
				else{
					int lo = 0;
					int hi = cur.size()-1;
 
					while(lo<hi){
						int mid = (lo+hi)/2;
						int l = mid;
						int r = mid+1;
						if(cur.get(r).d > - (q[ind]+1)){
							hi = l;
							continue;
						}
						int res = cmp(cur.get(l),cur.get(r),all.get((int)q[(int)ind]));
						if(res<0){
							hi = l;
						}
						else if(res==0){
							lo = l;
							hi = l;
						}
						else{
							lo = r;
						}
					}
					Pair got = ev(cur.get(lo),all.get((int)q[(int)ind]));
					long g = gc(got.first,got.second);
					num[ind] = got.first/g;
					dem[ind] = got.second/g;
				}
			}
		}
		cur.clear();
		for(int i = 0; i<li.size(); i++){
			Obj now = li.get(i);
			while(cur.size()>0){
				if(now.d > cur.get(cur.size()-1).d){
					cur.remove(cur.size()-1);
					continue;
				}
				if(cur.size()>1 && !used(now, cur.get(cur.size()-1), cur.get(cur.size()-2))){
					cur.remove(cur.size()-1);
					continue;
				}
				break;
			}
			cur.add(now);
			int ind = li.get(i).ind;
			if(a[ind]<a[(int)q[(int)ind]]){
				if(cur.get(0).d < -(q[ind]+1)){
					num[ind] = -1;
				}
				else{
					int lo = 0;
					int hi = cur.size()-1;
					while(lo<hi){
						int mid = (lo+hi)/2;
						int l = mid;
						int r = mid+1;
						if(cur.get(r).d < - (q[ind]+1)){
							hi = l;
							continue;
						}
						int res = cmp(cur.get(l),cur.get(r),all.get((int)q[(int)ind]));
						if(res<0){
							hi = l;
						}
						else if(res==0){
							lo = l;
							hi = l;
						}
						else{
							lo = r;
						}
					}
					Pair got = ev(cur.get(lo),all.get((int)q[(int)ind]));
					long g = gc(got.first,got.second);
					num[ind] = got.first/g;
					dem[ind] = got.second/g;
				}
			}
		}
		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("falling.out")));
		for(int i = 0; i<n; i++){
			if (num[i]==-1) out.println(-1);
			else out.println(num[i]+"/"+dem[i]);
		}
		out.close();
	}
}