Total Pride Value Computation

You are given an array of n fishes arranged from left to right. Each fish has an integer cuteness value (not necessarily distinct). For any contiguous subarray (interval) of the fish sequence, its pride value is defined as the number of inversion pairs in that subarray, i.e. the number of pairs of indices i and j within the subarray such that i < j and the left fish has a greater cuteness than the right fish.

There are a total of \( \frac{n(n+1)}{2} \) intervals. The total pride value is the sum of the pride values over all intervals. Equivalently, each inversion pair in the entire array (a pair \((i, j)\) with \(1 \le i < j \le n\) and \( a[i] > a[j] \)) contributes to every interval that covers both indices. In fact, each inversion pair \((i,j)\) is contained in \( i \times (n-j+1) \) intervals (when the fish positions are 1-indexed).

Your task is to compute the total pride value over all intervals.

inputFormat

The first line contains an integer n (the number of fishes).

The second line contains n space-separated integers, where the \(i\)-th integer represents the cuteness of the \(i\)-th fish from the left.

outputFormat

Output a single integer, the total pride value (i.e. the sum of inversion counts over all subarrays).

sample

3
1 2 3

0