P9143 [THUPC 2023 Preliminary] Mode

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.

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 one positive integer, the maximum value of $\sum_{i=1}^S \text{maj}(b_1,b_2,\cdots,b_i)$.

#### 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 . Translated by ChatGPT 5