I. Game, Set, Match
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The UTPC officers have arrived in Cincinnati! As avid tennis fans, they are very excited to watch the Cincinnati Masters 1000 tournament, the lead up event to the last grand slam of the year, the US Open.

One of the top players in the event, Carlos Alcaraz, is about to warm up for his first match. As part of the warmup, his coach, Juan Carlos Ferrero, has challenged him to a play a game that will stimulate his mind.

In this game, there are $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ piles of tennis balls, where the $$$i^\text{th}$$$ pile has $$$a_i$$$ balls. In one operation, Alcaraz adds the $$$\mathrm{MEX}^\dagger$$$ of the current pile sizes to his score and then chooses any pile and removes a single tennis ball from it. He keeps doing these operations until every pile is empty (has 0 balls). Alcaraz's goal is to maximize his score after all operations have taken place.

Watching Alcaraz play the game, the UTPC officers now wonder, what is the maximum score Alcaraz can achieve? Help Alcaraz maximize his score!

$$$^\dagger$$$The $$$\mathrm{MEX}$$$ (minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example:

  • The $$$\mathrm{MEX}$$$ of $$$[2, 2, 1]$$$ is $$$0$$$ because $$$0$$$ is not in the array.
  • The $$$\mathrm{MEX}$$$ of $$$[3, 1, 0, 1]$$$ is $$$2$$$ because $$$0$$$ and $$$1$$$ are in the array but $$$2$$$ is not.
  • The $$$\mathrm{MEX}$$$ of $$$[0, 3, 1, 2]$$$ is $$$4$$$ because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ are in the array but $$$4$$$ is not.
Input

The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of piles.

The next line contains $$$n$$$ numbers, $$$a_1, a_2, \dots, a_n$$$ $$$(0 \leq a_i \leq 10^6)$$$ — the number of tennis balls in each pile. Note that a pile can be empty to start.

Output

Output a single number, the maximum score Alcaraz can achieve.

Examples
Input
3
0 1 3
Output
9
Input
5
3 1 5 6 4
Output
54
Note

In the first test case, one sequence of operations Alcaraz can use is:

$$$[0, 1, 3]$$$ -> $$$[0, 1, 2]$$$ -> $$$[0, 1, 1]$$$ -> $$$[0, 1, 0]$$$ -> $$$[0, 0, 0]$$$

The MEX to start is 2. The MEX of the pile sizes after the operation sequence above is $$$3, 2, 2, 1$$$ in that order. Note that the MEX of $$$[0, 0, 0]$$$ is NOT added to the final answer, as no more operations can be done to remove tennis balls from any pile.

The score for this sequence of operations is $$$2 + 3 + 2 + 2 = 9$$$. It can be proven that this is the maximum score Alcaraz can achieve.