На координатной оси \(OX\) находятся \(n\) точек. \(i\)-я точка располагается в целочисленной координате \(x_i\) и имеет скорость \(v_i\). Гарантируется, что никакие две точки не располагаются в одной и той же координате. Все \(n\) точек двигаются с неизменной скоростью, координата \(i\)-й точки в момент времени \(t\) (\(t\) может быть нецелым) вычисляется как \(x_i + t \cdot v_i\).
Рассмотрим две точки \(i\) и \(j\). Пусть \(d(i, j)\) равно минимально возможной дистанции между этими двумя точками по всем возможным моментам времени (даже нецелым). Это значит, что если две точки \(i\) и \(j\) совпадут в какой-то момент времени, значение \(d(i, j)\) будет равно \(0\).
Ваша задача — посчитать значение \(\sum\limits_{1 \le i < j \le n}\) \(d(i, j)\) (сумму минимальных дистанций по всем парам точек).
Первая строка входных данных содержит одно целое число \(n\) (\(2 \le n \le 2 \cdot 10^5\)) — количество точек.
Вторая строка входных данных содержит \(n\) целых чисел \(x_1, x_2, \dots, x_n\) (\(1 \le x_i \le 10^8\)), где \(x_i\) равно изначальной координате \(i\)-й точки. Гарантируется, что все \(x_i\) различны.
Третья строка входных данных содержит \(n\) целых чисел \(v_1, v_2, \dots, v_n\) (\(-10^8 \le v_i \le 10^8\)), где \(v_i\) равно скорости \(i\)-й точки.
Выведите одно целое число — значение \(\sum\limits_{1 \le i < j \le n}\) \(d(i, j)\) (суммы минимальных дистанций по всем парам точек).
3 1 3 2 -100 2 3
3
5 2 1 4 3 5 2 2 2 3 4
19
2 2 1 -3 0
0
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач