Merge Sort and Inversion Count

You are given an array of integers. Your task is two-fold:

• Sort the array in non-decreasing order using the merge sort algorithm.
• Count the number of inversions in the array. An inversion is defined as a pair \((i, j)\) such that \(i a[j]\). In formula, the inversion count is given by \[ \text{Inversions} = \#\{(i,j)\mid 1 \leq i a[j]\} \]

The input is read from standard input and the output should be printed to standard output. The first line of input contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers. The output consists of two lines: the first line should display the sorted array (in ascending order) and the second line should display the inversion count.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\), the number of elements in the array.
2. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

The output should contain two lines:

1. The first line contains the sorted array (space-separated integers).
2. The second line contains a single integer, the inversion count.

## sample

5
1 2 3 4 5

1 2 3 4 5
0

</p>