Problem Description

You have several positive integers in $[1,n]$: for $1 \le i \le n$, you have $a_i$ copies of the integer $i$. Let $S = \sum_{i=1}^n a_i$.

For a sequence $p_1,p_2,\cdots,p_l$, define its mode $\text{maj}(p_1,p_2,\cdots,p_l)$ as the number that appears the most times. If multiple numbers are tied for the highest frequency, the largest of them is the mode.

Now you need to arrange these $S$ numbers into a sequence $b_1,b_2,\cdots,b_S$ such that $\sum_{i=1}^S \text{maj}(b_1,b_2,\cdots,b_i)$ is maximized. Output this maximum value.

Input Format

The first line contains an integer $n$, representing the value range.

The next line contains $n$ positive integers $a_1,a_2,\cdots,a_n$, representing the count of each number.

Output Format

Output one positive integer, the maximum value of $\sum_{i=1}^S \text{maj}(b_1,b_2,\cdots,b_i)$.

3
1 3 2

17

Hint

Sample Explanation 1

One sequence that achieves the maximum value is $(3,2,3,1,2,2)$.

Constraints

For all testdata, $1 \le n \leq 10^5$ and $1 \le a_1,a_2,\cdots,a_n \le 10^5$.

Source

From the 2023 Tsinghua University Student Algorithm Contest and Intercollegiate Invitational (THUPC2023) Preliminary Round.

Solutions and other resources can be found at https://github.com/THUSAAC/THUPC2023-Pre.

Translated by ChatGPT 5