Task A Gold USACO March

Problem 1: The Cow Run [Chris Tzamos, 2006]

Фермер Джон забыл заделать дыру в изгороди на своей ферме и его
N (1 <= N <= 1,000) коров сбежали и бедокурят. Каждая минута, когда
корова находится вне изгороди, она "бедокурит" на 1 доллар.
ФД должен посетить каждую корову, чтобы "усмирить" ее и прекратить
долларовые потери от нее.

К счастью, коровы находятся вдоль одной прямой на различных растояниях
от фермы. ФД знает расстояние P_i (-500,000 <= P_i <= 500,000, P_i != 0)
каждой коровы i относительно ворот (позиция 0), из которых он стартует.

ФД двигается на 1 единицу расстояния за минуту и "усмиряет" корову мгновенно.
Определите порядок, в котором ФД дожен посещать коров, так чтобы минимизировать
свои долларовые потери.

PROBLEM NAME: cowrun

INPUT FORMAT:

* Строка 1: Количество коров, N.

* Строки 2..N+1: Строка i+1 содержит целое число P_i.

SAMPLE INPUT (файл cowrun.in):

4
-2
-12
3
7

INPUT DETAILS:

Четыре коровы находтся в позициях: -2, -12, 3, и 7.

OUTPUT FORMAT:

* Строка 1: Минимальная общая стоимость долларовых потерь

SAMPLE OUTPUT (файл cowrun.out):

50

OUTPUT DETAILS:

Оптимальный порядок посещения --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 долларов.