Rearrange an Array to Minimize the Sum of Distinct Counts over All Prefixes

You are given an integer array `nums` and may rearrange its elements into any order. For an arrangement `a` of length `n`, its cost is the sum, over every prefix `a[0..i]` for `i` from `0` to `n - 1`, of the number of distinct values in that prefix. Return the minimum cost over all arrangements of `nums`. ### Function Signature ```python def min_prefix_distinct_sum(nums: list[int]) -> int: ``` ### Rules - Every element is used exactly once; equal values are interchangeable. - The number of distinct values in a prefix counts each value once, however many times it appears in that prefix. - Return only the minimum cost, a single integer, not the arrangement, so the answer is unique even when several arrangements reach it. ### Constraints - `1 <= len(nums) <= 10^5` - `-10^9 <= nums[i] <= 10^9` - The answer can exceed `2^31 - 1`: when all `n` values are distinct it is `n * (n + 1) / 2`, which is `5,000,050,000` for `n = 10^5`. Use a 64-bit integer; the answer always stays below `2^53`. ### Examples **Example 1** ```text Input: nums = [1, 2, 2, 3, 3, 3] Output: 10 ``` In the given order the prefix distinct counts are `1, 2, 2, 3, 3, 3`, a cost of `14`. The arrangement `[3, 3, 3, 2, 2, 1]` has counts `1, 1, 1, 2, 2, 3`, a cost of `10`, and no arrangement does better. **Example 2** ```text Input: nums = [4, 1, 4, 1] Output: 6 ``` The given order costs `1 + 2 + 2 + 2 = 7`; `[4, 4, 1, 1]` costs `1 + 1 + 2 + 2 = 6`, the minimum. **Example 3** ```text Input: nums = [9, -2, 5] Output: 6 ``` All values are distinct, so every arrangement costs `1 + 2 + 3 = 6`.