No Thanks!

Interview

Time limit1sMemory limit512 MB

Summary

Given a set of distinct card numbers, score the pile as the sum of each card that does not have a consecutive predecessor among the collected cards.

Level: Easy3 of 10
Topics: Hash map, Array, Implementation
Solved: No attempts yet

Problem

In the card game “No Thanks,” the deck consists of $36$ cards numbered $1$ through $36$ , and players collect cards into their score pile as the game is played. A player’s final score is the sum of the numbers on the collected cards, with one exception: if a player has collected any cards with two or more consecutive numbers, only the smallest number in that group counts toward the score. Your job is to compute the score for a single player’s pile of cards, though here the deck may be much larger than $36$ cards.

Input

The first line contains one integer, $n$ , the number of cards collected. The second line contains $n$ integers, the numbers on the collected cards. You may assume that $1 \le n \le 90\,000$ , all card values are in the range $1 \dots 90\,000$ inclusive, and no card value is repeated.

Output

Output a single line containing the score for the given set of cards.

Examples2

Example 1
Input
```
5
1 7 5 3 4
```
Expected output
```
11
```
Example 2
Input
```
6
2 1 3 8 4 5
```
Expected output
```
9
```