红军打水
Description:
“好消息，红军来我们村啦！”
这一天，小王的村子里迎接了一批战士，他们刚刚打了一场胜仗，正在往本部移动，路经小王所在的村庄想要稍作休整。村民们非常热情，纷纷打开门来迎接这些战士，并且拿出了家里的粮食招待他们。我们的战士当然不想白吃白喝，经过讨论，战士们发现村民里的水桶都已经空了，于是决定为村民们打水。但是村子里只有一口井，而村民家里的水桶大小不一，所以战士们打水的花费时间也不同，并且前面的人在打水的时候，后面排队的人必须等待，你作为班长，想让战士们等待的平均时间最短，以空出时间完成其他任务。请你给拿好水桶的战士们排个队，保证结果战士们等待的平均时间最短。
Input:
第一行为一个整数 n,表示战士人数。
第二行 n个整数，第 i个整数Ti 表示第 i个人的花费时间 Ti。
（1<=n <=1e6,1<=Ti<=100）
Output:
输出结果保留整数，输出最短平均等待时间。
Sample Input:
3 56 12 1
Sample Output:
4
Hint:
样例解释：第一个人等了0，第二个人等了1，第三个人等了13，（0+1+13）/3 = 4
Submit