Minimum Adjacent Swaps to Sort

You are given a sequence of n integers. Your task is to compute the minimum number of adjacent swaps required to sort the sequence in non-decreasing order. It can be shown that the minimum number of adjacent swaps required is equal to the number of inversions in the sequence.

An inversion is a pair of indices \( (i, j) \) such that \( i a_j \). Mathematically, the number of inversions \( Inv \) in an array \( a \) is given by:

$$Inv = \sum_{i=1}^{n} \sum_{j=i+1}^{n} 1_{(a_i > a_j)} $$

Your goal is to calculate this value.

inputFormat

The input is given from standard input (stdin) and consists of two lines:

• The first line contains an integer \( n \) (\( 1 \leq n \leq 10^5 \)), representing the number of elements in the sequence.
• The second line contains \( n \) space-separated integers \( a_1, a_2, \dots, a_n \) representing the sequence.

outputFormat

Output to standard output (stdout) a single integer, which is the minimum number of adjacent swaps required to sort the sequence.

## sample

5
5 4 3 2 1

10