3708: 拆分(第一轮02)
题目描述
鸡尾酒又带着大家学习新定义啦！ 今天要学习的内容是集合的 mex ，集合的 mex 指的 是 一 个 集合没 有 出现过 的 最小自 然 数。例 如 ， mex({1,2}) = 0 、mex({0,1,2,3}) = 4。
现在你有一个包含 n 个元素的集合，你可以将它分成任意个数量的新集合， 使 得所有新集合的 mex 值之和最大，求这个最大值是多少。
输入
第一行输入一行一个正整数 n， 接下来一行包含 n 个非负整数， 表示集合中的 元素 ai 。
输出
输出一行一个整数表示答案。
样例输入 复制
5
0 0 1 1 2样例输出 复制
5提示
【样例 1 输入】
5
0 0 1 1 2
【样例 1 输出】
5
【样例 1 说明】
分成两个集合 {0, 1}, {0, 1, 2}, 第一个集合的 mex 为 2，第二个集合的 mex 为 3 ，两个集合的 mex 之和为 5 ，这样分集合是最大的。当然也可以分成 {0}, {0}, {1}, {1}, {2}，但是这样五个集合的 mex 之和为1 + 1 + 0 + 0 + 0 = 2。
【样例 2 输入】
5
1 2 3 4 5
【样例 2 输入】
0
【样例 2 说明】
因为原集合没有 0，所以无论怎么分集合，每一个新集合都不会有 0，所以每一 个集合的 mex 都为 0，答案一定为 0。
【数据范围】
本题共有 10 个测试点 第一个测试点有 0 < ai 第二个测试点有 ai = 0
第 3 − 4 个测试点有 0 ≤ ai ≤ 1
对于所有测试点，有 1 ≤ n ≤ 10^5, 0 ≤ ai ≤ 1000