Counting Inversions in an Array

Given an array of integers, your task is to count the number of inversions in the array.

An inversion is defined as a pair of indices \( (i, j) \) such that \( i a[j] \). In other words, it quantifies how far (or close) the array is from being sorted.

inputFormat

The input is read from stdin and follows the format below:

1. The first line contains a single integer \( n \) (with \( 0 \leq n \leq 10^5 \)), which is the number of elements in the array.
2. The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output to stdout a single integer that represents the number of inversions in the given array.

5
2 3 8 6 1

5