Boredom

Back to problems

Codeforces

Medium

Arrays

Dynamic Programming

Math

Google

Boredom

Choose numbers to maximize total score, but taking a value removes its neighbors.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Codeforces 455A

gfg

Problem Statement

You are given an array of integers. You may choose any integer value $x$ and gain points equal to the sum of all occurrences of $x$ in the array. However, after choosing $x$ , you are not allowed to choose $x-1$ or $x+1$ .

Your task is to compute the maximum total points you can obtain.

This is equivalent to picking a set of values so that no two chosen values differ by exactly 1, while maximizing the total weight collected from all occurrences of the chosen values.

Input Format

The first line contains an integer $n$ — the number of elements in the array.
The second line contains $n$ integers $a_i$ .

Output Format

Print one integer: the maximum points that can be obtained.

Constraints

$1 \le n \le 10^5$
$1 \le a_i \le 10^5$

Examples

Sample cases returned by the problem API.

Example 1

Input

5
1 2 3 1 3

Output

Explanation

Take value 1 for 2 points and value 3 for 6 points would conflict with 2, but the best choice is taking only value 3 or value 1 and 3 are adjacent? Actually 1 and 3 do not conflict. Total from 1 is 2 and from 3 is 6, so the best score is 8.

Example 2

Input

4
1 2 3 4

Output

Explanation

Take values 2 and 4, or 1 and 3. The best is 2 + 4 = 6.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress