小灿的危机

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

小灿成功的活了下来,逼供无效后,残忍的小铭决定把小灿做成食品,然后去银河交易中心贩卖,因为这是刘宝宝黑粉集团的主要经济来源,所以还有很多人也会被做成食品,但是刘宝宝的黑粉们很蠢,他们只有一个把人做成食品的机器,还因为每个人的肉质不同,骨头的坚硬度不同,所以每一个人被处理的时间也不同。现在小灿想知道如果他前面的n个人可以被随便改变顺序,那么每一个人的等待时间之和最小是多少。小灿托梦给了你,希望你来帮帮他。

Description

给出人数n以及每一个人的处理时间ai,求所有人的等待时间之和。

Input

第1行一个数,表示共有n个人。
第2行n个数,第i个数表示第i个人的处理时间

Output

一个整数,所有人的等待时间之和(小灿不算在所有人内)

Sample 1

Input

5
5 4 3 2 1

Output

20

Output explanation

队伍的顺序是:第5 个,第4 个,第3 个,第2 个,第1 个。
第5 个人的等待时间为0,结账时间为1
第4 个人的等待时间为1,结账时间为2
第3 个人的等待时间为1+2=3,结账时间为3
第2 个人的等待时间为1+2+3=6,结账时间为4
第1 个人的等待时间为1+2+3+4=10,结账时间为5

Limitation

1000ms, 512MB

Hint

30% n<=5.
100% n<=100000,ai<2333333.

noip每天第1题难度题比赛

未参加
状态
已结束
规则
OI
题目
3
开始于
2017-11-04 14:00
结束于
2017-11-04 18:00
持续时间
4.0 小时
主持人
参赛人数
9