Maximizing the Sum of Prefix Modes

You are given several positive integers in the range \( [1,n] \). For each \( i \) where \( 1 \le i \le n \), you have \( a_i \) copies of the integer \( i \). Let \( S = \sum_{i=1}^{n} a_i \) be the total number of elements.

For any sequence \( p_1, p_2, \dots, p_l \), define its mode \( \text{maj}(p_1, p_2, \dots, p_l) \) as the number that appears most frequently. In the case of a tie, the mode is defined as the largest among those numbers.

You need to arrange all the \( S \) numbers into a sequence \( b_1, b_2, \dots, b_S \) so that the value \[ \sum_{i=1}^{S} \text{maj}(b_1, b_2, \dots, b_i) \] is maximized. Output this maximum possible sum.

Hint: A descending order arrangement (placing all copies of the largest numbers first) turns out to be optimal.

inputFormat

The first line contains a single integer \( n \) indicating the range of numbers.

The second line contains \( n \) space‐separated positive integers: \( a_1, a_2, \dots, a_n \), where \( a_i \) is the count of integer \( i \).

outputFormat

Output a single integer representing the maximum possible sum of the prefix modes.

sample

2
2 1

5