#P18884. [2026多校联测]众数

[2026多校联测]众数

众数(mode)

题目描述

你有若干个 [1,n][1,n] 内的正整数:对于 1≤i≤n1 \le i \le n,你有 aia_i 个整数 ii。设 S=∑i=1naiS = \sum_{i=1}^n a_i。

对于一个序列 p1,p2,⋯ ,plp_1,p_2,\cdots,p_l,定义其众数 maj(p1,p2,⋯ ,pl)\text{maj}(p_1,p_2,\cdots,p_l) 为出现次数最多的数。若有多个数出现次数最多,则其中最大的数为其众数。

现在你需要把这 SS 个数排成一个序列 b1,b2,⋯ ,bSb_1,b_2,\cdots,b_S,使得 ∑i=1Smaj(b1,b2,⋯ ,bi)\sum_{i=1}^S \text{maj}(b_1,b_2,\cdots,b_i) 最大。输出该最大值。

输入格式

第一行一个整数 nn,表示值域。

接下来一行 nn 个正整数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n,表示每种数的个数。

输出格式

输出一行一个正整数表示 ∑i=1Smaj(b1,b2,⋯ ,bi)\sum_{i=1}^S \text{maj}(b_1,b_2,\cdots,b_i) 的最大值。

输入输出样例 #1

3
1 3 2
17

说明/提示

样例解释 1

一个达到最大值的序列为 (3,2,3,1,2,2)(3,2,3,1,2,2)。

数据规模

0∼10%0 \sim 10 \%:∑ai≤10\sum a_i \leq 10

10%∼20%10 \% \sim 20 \%:∑ai≤20\sum a_i \leq 20

20%∼30%20 \% \sim 30 \%:1≤n≤201 \leq n \leq 20

30%∼50%30 \% \sim 50 \%:1≤n≤50001 \leq n \leq 5000

50%∼60%50 \% \sim 60 \%:保证 aia_i 单调不增

对于 100%100 \% 的数据,保证 1≤n≤105,1≤ai≤1051 \leq n \leq 10^5, 1 \leq a_i \leq 10^5