Падающие порталы
Имеется n миров, в каждом из которых есть портал. Первоначально мир i (для 1 ≤ i ≤ n) находится в x - координате i и y - координате A[i] (1 ≤ A[i] ≤ 10^9). Также в каждом мире есть корова. В момент времени 0 все y - координаты различны, и миры начинают падать: мир i непрерывно движется в отрицательном y направлении со скоростью i единиц в секунду.
В любое время, когда два мира находятся в одной и той же y-координате (возможно в дробное время), порталы "выравниваются". Это означает, что корова в одном из миров может мгновенно переместиться в другой мир.
Для каждого значения i корова в мире i хочет отправиться в мир Q[i] (Q[i] ≠ i). Помогите каждой корове определить, сколько времени займет ее путь, если она будет двигаться оптимально.
Каждый ответ на запрос должен быть дробью a / b, где a и b - положительные и взаимно простые целые числа, или -1, если путешествие невозможно.
Входные данные
Первая строка содержит единственное целое число n (2 ≤ n ≤ 2 * 10^5). Следующая строка содержит n целых чисел A[1], A[2], ..., A[n]. В следующей строке записано n целых чисел Q[1], Q[2], ..., Q[n].
Выходные данные
Выведите n строк, i - ая из которых содержит длину пути коровы i.