Inverse Pair Count

Given a sequence of positive integers, count the number of inversion pairs in the sequence. An inversion pair is defined as an ordered pair of elements \(a_i\) and \(a_j\) such that \(a_i > a_j\) and \(i < j\). Note that the sequence may contain duplicate numbers.

This problem is a classical application of the merge sort technique to count inversions efficiently in \(O(n \log n)\) time.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\) which is the number of elements in the sequence.
2. The second line contains \(n\) positive integers separated by spaces.

outputFormat

Output a single integer which represents the number of inversion pairs in the sequence.

sample

5
1 3 2 3 1

4