题目描述

超市的收银处有 n 位顾客在排队等着付款，他们的编号依次为：1, 2, …, n。

由于每个顾客所购商品不同，付款所需时间也不同。给出这 n 位顾客每人单独付款所需的时间。

顾客付款的顺序会影响总的等待时间。请你计算所有顾客总等待时间的最小值。

输入格式

共 2 行：

• 第一行为一个正整数 n（1 ≤ n ≤ 100），表示排队的人数；
• 第二行为 n 个由空格分隔的正整数，表示每位顾客单独付款所需的时间（每个时间 ≤ 15）。

输出格式

输出 1 行，表示所有顾客总的最少等待时间。

输入样例 #1

4  
1 2 1 2

输出样例 #1

7

题目说明

将付款时间排序后按顺序排队可以使总等待时间最小。
如样例中顾客付款时间排序为：1 1 2 2。

等待时间为：

• 第 1 位顾客等待 0；
• 第 2 位顾客等待 1；
• 第 3 位顾客等待 1 + 1 = 2；
• 第 4 位顾客等待 1 + 1 + 2 = 4；

总等待时间为 0 + 1 + 2 + 4 = 7。