You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

农夫约翰的牧场围栏上出现了一个洞，有 $N$（$1\le N\le 1000$）只牛从这个洞逃出了牧场。这些出逃的奶牛很狂躁，他们在外面到处搞破坏，每分钟每头牛都会给约翰带来 $1$ 美元的损失。约翰必须用缰绳套住所有的牛，以停止他们搞破坏。

幸运的是，奶牛们都在牧场外一条笔直的公路上，牧场的大门恰好位于公里的 $0$ 点处。约翰知道每头牛距离牧场大门的距离 $P_i$（$-5\times10^5\le P_i\le5\times 10^5, P_i\ne0$）。

约翰从农场大门出发，每分钟移动一个单位距离，每到一头牛所在的地点，约翰就会给它套上缰绳，套缰绳不花时间。按怎样的顺序去给牛套缰绳才能使约翰损失的费用最少？

输入格式

第一行：奶牛的数目，$N$。

第二至 $N+1$ 行：第 $i+1$ 行包含整数 $P_i$。

输出格式

一行，表示约翰最小的损失。

4 
-2 
-12 
3 
7 

50 

提示

四头奶牛所在坐标分别为 $-2, -12, 3, 7$。

最优的访问顺序为 $-2, 3, 7, -12$。 FJ 在第 $2$ 分钟到达了位置 $-2$，在这个位置的奶牛造成了 $2$ 美元的损失。

然后他去了距离为 $5$ 的位置 $3$，这头牛总共造成了 $2+5 = 7$ 美元的损失。

他又花了 $4$ 分钟到达了 $7$，这里造成了 $7 + 4 = 11$ 美元的损失。

最后他用 $19$ 分钟到达了位置 $-12$，损失了 $11 + 19 = 30$ 美元。

总的损失为 $2 + 7 + 11 + 30 = 50$ 美元。