На координатной оси \(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)\) (сумму минимальных дистанций по всем парам точек).
Выходные данные
Выведите одно целое число — значение \(\sum\limits_{1 \le i < j \le n}\) \(d(i, j)\) (суммы минимальных дистанций по всем парам точек).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 3 2
-100 2 3
|
3
|
|
2
|
5
2 1 4 3 5
2 2 2 3 4
|
19
|
|
3
|
2
2 1
-3 0
|
0
|