Question:
Significant Inversions Algorithm : Inversion Pairs
You are given a sequence of n distinct numbers A1, ... , An. An inversion is a pair i < j such that Ai > Aj. Call a pair (i, j) a significant inversion if i < j and Ai > 2*Aj. Give an O(n*log(n)) algorithm to count the number of significant inversions in the input sequence.