← 返回题目列表

Codeforces · 455/A

A. 无聊

中文机器翻译题面 查看原题

亚历克斯不喜欢无聊。这就是为什么每当他感到无聊时,他就会想出游戏。在一个漫长的冬夜,他想出了一个游戏并决定玩它。

给定一个由 n 个整数组成的序列 a。玩家可以执行多个步骤。在一个步骤中,他可以选择序列中的一个元素(让我们将其表示为 ak)并将其删除,此时所有等于 ak + 1 和 ak - 1 的元素也必须从序列中删除。这一步会给玩家带来 ak 点。

Alex 是一位完美主义者,因此他决定获得尽可能多的分数。帮助他。

输入

第一行包含整数 n (1 ≤ n ≤ 105),显示 Alex 的序列中有多少个数字。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 105)。

输出

打印一个整数——Alex 可以获得的最大分数。

示例

输入 #1

2
1 2

输出 #1

2

输入 #2

3
1 2 3

输出 #2

4

输入 #3

9
1 2 1 3 2 2 2 2 3

输出 #3

10

注意

考虑第三个测试示例。第一步,我们需要选择任何等于 2 的元素。在这一步之后,我们的序列看起来像这样 [2, 2, 2, 2]。然后我们执行 4 个步骤,在每个步骤中我们选择任何等于 2 的元素。总共我们获得 10 分。