题解 | #计算数组的小和#

n = int(input())
nums = list(map(int, input().split()))
def merge_sort(left, right):
    if left >= right:
        return 0
    m = (left + right) // 2
    res = merge_sort(left, m) + merge_sort(m + 1, right)
    i, j = left, m + 1
    temp = [0] * (right - left + 1)
    index = 0
    while i <= m and j <= right:
        if nums[i] <= nums[j]:
            res += nums[i] * (right - j + 1)
            temp[index] = nums[i]
            index += 1
            i += 1
        else:
            temp[index] = nums[j]
            j += 1
            index += 1
    while j < right + 1 or i < m + 1:
        if i < m + 1:
            temp[index] = nums[i] 
            i += 1
        else:
            temp[index] = nums[j]
            j += 1
        index += 1
    nums[left:right + 1] = temp
        
    return res
print(merge_sort(0, len(nums) - 1))