Description

超市的收银处有 n 位顾客在排队等着付款，他们的编号依次为 1,2，…，n。由于每个顾客所购的商品不同，因此付款时所需的等待时间也就不一样。给出这 n 个人每个人单独付款所需的时间。而顾客不同的付款顺序，所有顾客总等待时间是不一样的，收银员想知道所有顾客总等待时间最少是多少。

Input Format

共2行，第一行为正整数n，表示排队的人数；第二行n个由空格分隔的正整数，分别为这n个人单独付款所需的时间。

Output Format

共 1 行 1 个数，表示所有顾客总的最少等待时间。

4
1 2 1 2

7

Hint

样例解释:按顾客编号，排队顺序为 1 3 2 4，排序后第一位顾客不需要等待，第二位顾客需要等待时间为 1，第三位顾客需要等待时间为 1+1，第四位顾客需要等待时间为 1+1+2。总等待时间为 7。
数据范围:
1≤n≤100，每位顾客单独付款所需的时间≤150

Source

合肥市2019信息学 贪心 前缀和