Tokens at the Fair


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++

At a science fair in Puerto Rico, you play a game with n tokens, each marked with a positive integer. In one move, choose a token with value x: earn x points and remove that token. Also remove every remaining token with value x - 1 or x + 1. Other tokens with value x remain available.

You may make as many moves as you wish, including none. Find the maximum total score.

Input

The first line contains n. The second contains n integers a[1], a[2], …, a[n].

Output

Print one integer: the maximum total score. It may exceed the range of a signed 32-bit integer.

Constraints

1 ≤ n ≤ 100 000; 1 ≤ a[i] ≤ 100 000.

Execution limits

2 s · 256 MiB

Ejemplo
Input Example Output Example
6
2 2 3 3 3 4
9

Choosing the three tokens with value 3 earns 9 points. Choosing values 2 and 4 earns only 8.

Source

Adapted for OiPR 2026. Codeforces 455A — Boredom.


Comments

There are no comments at the moment.