Merge Sort and Inversion Count

You are given an array of n integers. Your task is to sort the array in non-decreasing order using the merge sort algorithm and count the number of inversions in the original array.

An inversion is defined as a pair of indices \( (i, j) \) such that \( i a[j] \). The total number of such pairs is called the inversion count. For example, in the array [3, 1, 2], there are two inversions: \( (3,1) \) and \( (3,2) \).

You need to implement the merge sort algorithm that will not only sort the array but also count the inversions. The efficiency of your solution will be tested with both small and large input sizes.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \( n \), the number of elements in the array.
• The second line contains \( n \) space-separated integers representing the array.

outputFormat

The output should be written to stdout in the following format:

• The first line should contain the sorted array (space-separated).
• The second line should contain the inversion count.

## sample

5
1 2 3 4 5

1 2 3 4 5
0

</p>