Problem A: A任务执行

上一题 正确率: $160.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $5$ 正确数量 $8$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

有n个不同的任务需要完成，完成任务需要耗费一定的时间。一旦开始进行某个任务，既不能中途暂停 或终止这个任务，也不能同时进行另一个任务。此外，每当一个耗时不为0的任务被完成，剩余的其他 任务所需要的时间都减少1（最低减至0，先前已经完成的任务不受影响）。 给出所有任务的耗时，请求出完成它们所需的最短时间。

Input

输入的第1行包含1个整数n，表示任务数。 接下来1行，包含n个整数，第i个整数表示完成第i个任务所需要的时间。

Output

求出完成它们所需的最短时间。

Sample Input复制

6
1 1 4 5 1 4

Sample Output复制

8

提示


• 1 ≤ n ≤ 10^5 

• 1 ≤ ai ≤ 10^9 

• 有30%的数据，n ≤ 10


一种可能的方案是：
1. 完成一个耗时为1的任务，剩下的任务分别耗时0, 3, 4, 0, 3；
2. 完成两个耗时为0的任务，剩下3, 4, 3；
3. 完成一个耗时为4的任务，剩下2, 2；
4. 完成一个耗时为2的任务，剩下1；
5. 完成一个耗时为1的任务。
这个方案的总耗时是1 + 0 + 0 + 4 + 2 + 1 = 8。不存在总耗时小于8的方案。