CF455A.Boredom

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.

Given a sequence aa consisting of nn integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it aka_{k} ) and delete it, at that all elements equal to ak+1a_{k}+1 and ak1a_{k}-1 also must be deleted from the sequence. That step brings aka_{k} points to the player.

Alex is a perfectionist, so he decided to get as many points as possible. Help him.

输入格式

The first line contains integer nn ( 1<=n<=1051<=n<=10^{5} ) that shows how many numbers are in Alex's sequence.

The second line contains nn integers a1a_{1} , a2a_{2} , ..., ana_{n} ( 1<=ai<=1051<=a_{i}<=10^{5} ).

输出格式

Print a single integer — the maximum number of points that Alex can earn.

输入输出样例

  • 输入#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
    

说明/提示

Consider the third test example. At first step we need to choose any element equal to 22 . After that step our sequence looks like this [2,2,2,2][2,2,2,2] . Then we do 44 steps, on each step we choose any element equals to 22 . In total we earn 1010 points.

首页