4. Recall the problem of counting the number of inversions, in which we are given a sequence of n numbers a1,,an, for which we assume are all distinct. Because some people may feel that counting inversions is too sensitive of a measure for how different two ordering are, we are going to modify the problem a little. Let's call a pair i2aj. Give an O(nlogn) algorithm to count the number of significant inversions between two orderings. (Hint: Similar to counting normal inversions, do the merge sort together with counting significant inversions at the same time. However, you may want to count "across-half" significant inversions separately from merging the two lists unlike in the ordinary Merge-and-Count. Alternatively, it is possible to count across-half significant inversions together with merging the lists but doing so is a bit more complicated.) 5. Implement the divide and conquer algorithm for counting the number of inversions in your chosen programming language. You may choose to read the input from either the keyboard or a file as before. Submit your code and the outputs of your code on a few sample inputs