Фермер Джон забыл заделать дыру в изгороди на своей ферме и его N (1 <= N <= 1,000) коров сбежали и бедокурят. Каждая минута, когда корова находится вне изгороди, она "бедокурит" на 1 доллар. ФД должен посетить каждую корову, чтобы "усмирить" ее и прекратить долларовые потери от нее.
К счастью, коровы находятся вдоль одной прямой на различных растояниях от фермы. ФД знает расстояние Pi (-500,000 <= Pi <= 500,000, Pi != 0) каждой коровы i относительно ворот (позиция 0), из которых он стартует.
ФД двигается на 1 единицу расстояния за минуту и "усмиряет" корову мгновенно. Определите порядок, в котором ФД дожен посещать коров, так чтобы минимизировать свои долларовые потери.
PROBLEM NAME: cowrun
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..N+1: Строка i+1 содержит целое число Pi.
Формат выходных данных
* Строка 1: Минимальная общая стоимость долларовых потерь
Примечание
Оптимальный порядок посещения --2, 3, 7, -12. ФД прибудет в позицию -2 на 2-ой минуте и получит ущерб в два доллара от этой коровы.
Потом он проследует в позицию 3 (расстояние 5), итого ущерб = 2+5=7 долларов от второй коровы.
Затем он потратит 4 минут чтобы добраться до коровы в позиции 7, с общей стоимостью потерь от этой коровы 7+4 = 11 долларов.
Наконец, он потратит 19 минут чтобы перейти в точку -12, и стоимость потерь от этой коровы будет 11 + 19 = 30 долларов.
Общие потери от всех коров будут 2 + 7 + 11 + 30 = 50 долларов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
-2
-12
3
7
|
50
|