Time limit: 5000ms
Memory limit: 256mb

Description:

For an array arr[] with n positive integers, its inversion count is defined as the number of distinct pairs of elements (arr[i], arr[j]) where arr[i] > arr[j] and i < j. Inversion count is a metric of measuring how far the array is from being sorted in ascending order. If the array is already sorted in ascending order, then the inversion count is 0, but if the array is sorted in descending order, the inversion count is the maximum, and named as maximum inversion count.

In this exercise, given n and arr[], we want to find the inversion count and the maximum inversion count of arr[]. The main function has been provided. You are required to complete two functions, namely merge_sort_and_count() and get_max_num_inv(). For merge_sort_and_count(), your code should (1) merge twos subarray in arr[] defined by left, mid and right using a temporary array t[], (2) compute the inversion count num_inv, and (3) returns num_inv. For get_max_num_inv(), your code should compute the maximum inversion count given an array arr[].


Sample Input 1:
4
9 7 5 3

Sample Output 1:
Input the number of integers:
Input these integers:
Inversion Count:
6
Maximum Inversion Count:
6

Explanation: The given array has six inversions: (9, 7), (9, 5), (9, 3), (7, 5), (7, 3), and (5, 3), which is also the maximum possible.


Sample Input 2:
5
2 2 1 3 4

Sample Output 2:
Input the number of integers:
Input these integers:
Inversion Count:
2
Maximum Inversion Count:
9

Explanation: The given array has two inversions: (2, 1) and (2, 1). The maximum inversion count is from (4,3), (4,2), (4,2), (4,1), (3,2), (3,2), (3,1), (2,1), (2,1) (for [4, 3, 2, 2, 1]). 


Code Template:

#include <stdio.h>
#include <stdlib.h>

int merge_sort_and_count(int arr[], int t[], int left, int right){
    int mid, num_inv = 0, curr_num_inv = 0;
    if (right > left) {
        mid = (right + left) / 2;
        num_inv = merge_sort_and_count(arr, t, left, mid);
        num_inv += merge_sort_and_count(arr, t, mid + 1, right);
        
        // code here

        num_inv += curr_num_inv;

    }

    return num_inv;
}

int get_max_num_inv(int arr[], int n){
    int max_num_inv = 0;
    
    // code here

    return max_num_inv;
}

int get_num_inv(int arr[], int n)
{
    int t[n];
    return merge_sort_and_count(arr, t, 0, n - 1);
}

int main()
{
    int n, *arr, *t;
    printf("Input the number of integers:\n");
    scanf("%d",&n);
    arr = (int*)malloc(sizeof(int)*n);
    t = (int*)malloc(sizeof(int)*n);
    printf("Input these integers:\n");
    for(int i=0; i<n; i++)
        scanf("%d", &arr[i]);
    printf("Inversion Count:\n%d\n", get_num_inv(arr, n));
    printf("Maximum Inversion Count:\n%d\n", get_max_num_inv(arr, n));
    return 0;
}