等候时间

题目描述

有 $n$ 艘货船到达某港口，此港口只能一船一船进港卸货，需要安排货船的进港次序。每艘货船卸货所需的时间是已知的，有一种卸货顺序能使 $n$ 艘货船的等候时间的总和最少。

童童想知道这个最少的等候时间总和是多少，每艘船的等候时间为前一艘船的卸货时间，如第一艘货船的等候时间为 $0$，第二艘货船的等候时间为第一艘货船的卸货时间，第三艘货船的等候时间为第二艘货船的卸货时间，以此类推。

输入格式

共两行。

第一行，一个正整数 $n$，表示货船的数量。

第二行，$n$ 个正整数 $x$，表示每艘货船卸货所需的时间，数与数之间以一个空格隔开。

输出格式

一行，一个正整数，表示所有货船最少的等候时间之和。

样例输入 #1

5
1 5 1 2 1

样例输出 #1

5

样例输入 #2

3
3 1 2

样例输出 #2

1

数据范围

$1 \le n \le 500$，$1 \le x \le 1000$

知识点与难度

本题涉及的知识点从属于 GESP五级（贪心基础、排序基础），难度等级：⭐⭐⭐。

测试点分布