Minimum Sum of Prefix Distinct Counts

You are given an integer array nums. You may rearrange its elements into any order.

For an arrangement a, the distinct count of index i is the number of different values among a[0], a[1], ..., a[i]. The score of the arrangement is the sum of the distinct counts of all indices.

Return the minimum possible score over all arrangements of nums.

Examples

Example 1

Input: nums = [2, 2, 3, 4, 5, 5]
Output: 13
Explanation: The arrangement [2, 2, 5, 5, 3, 4] has distinct counts [1, 1, 2, 2, 3, 4], which sum to 13. No arrangement scores less.

Example 2

Input: nums = [1, 2, 3]
Output: 6
Explanation: All values are different, so the distinct counts are always [1, 2, 3].

Example 3

Input: nums = [7, 7, 7, 7]
Output: 4
Explanation: Only one value exists, so every distinct count is 1.