1. Suppose we are given an array of n integers: a1,a2,...,an .

   An inversion is a pair i < j such that a_i > a_j. Counting inversions is a good measure of sortedness of the array. However, one might feel that this measure is too sensitive. Let us call a pair a significant inversion if i < j and a_i > 2a_j. Give an O(nlogn) divide and conquer algorithm for counting the number of significant inversions.