Consider an array with values with unsorted values. Write a java function public static int countBad(int[] hs) that takes an array of n numbers and returns the number of pairs 0 i < j < n such that hs[i] < hs[j]. (ie. if the previous entry in the array is less than the next value).

For example (abusing Javas array notation):

countBad({35, 22, 10}) == 0

countBad({3,1,4,2}) == 3

countBad({5,4,11,7}) == 4

countBad({1, 7, 22, 13, 25, 4, 10, 34, 16, 28, 19, 31}) == 49

We expect your code to run in at most O(n logn) time, where n is the length of the input array.

(Hint: Write a merge-like algorithm that computes two things: (1) the combined sorted list in descending order and (2) the number of inverted pairs. When youre done, it should look almost identical to the merge sort algorithm except it computes this additional thing.)

How to return two values?

There are many ways one can return multiple values. You can, for example, return an array of length 2new int[]{25, 14};

Or, you can write a Pair class (as an inner class).