Besley the squirrel has a pile of ~N~ acorns, each with a size ~a_1, \dots, a_n~. Besley is willing to sell all the acorns to Wesley at a price equal to its size, that is the ~i^{th}~ acorn costs ~a_i~ dollars.

Each acorn happens to be hollow on the inside, allowing for any acorn to be placed inside another acorn if one is strictly smaller than the other.

If Wesley places an acorn of size ~a_i~ inside another acorn of size ~a_j~ where ~a_i < a_j~ then he can buy both acorns for a cost of ~a_j~ dollars, as Wesley is convinced that Besley won't play any shenanigans.

Wesley can repeat this process as many times as he wants before he buys an acorn, or choose not to place any acorns inside another.

It must hold for all acorns that if an acorn contains other acorns, the acorns contained must all be strictly smaller in size and must all be distinct in size, that is, there cannot be two acorns nested at the same level.

Can you help Wesley determine the minimum cost required in order to purchase all the acorns?

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

~1 \le N \le 1\,000~
~1 \le a_i \le 1\,000\,000~ for all ~1 \le i \le N~

Subtask 1 [50%]

~1 \le a_i \le 2~ for all ~1 \le i \le N~

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line will contain ~N~, representing the number of acorns.

The second line will contain ~N~ integers, ~a_1, \dots, a_n~, representing the sizes of each acorn.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output, on a single line, the minimum cost required for Wesley to buy all the acorns.

Sample Input 1

4
1 2 2 1

Sample Output 1

4

Sample Input 2

5
1 2 3 2 1

Sample Output 2

5

Sample Explanation 2

Besley can place acorn ~a_1~ in acorn ~a_2~ and acorn ~a_5~ in acorn ~a_4~. He can then place either acorn ~a_2~ or acorn ~a_4~ in acorn ~a_3~, but not both.

The cost ends up being 5 dollars from 3 + 2.

Sample Input 3

6
2 4 6 1 2 3

Sample Output 3

8

Sample Explanation 3

Besley can end with two acorns of sizes 6 and 2 for a cost of 8 dollars.