Sherlock and Inversions

After a long series of jobless days, Sherlock and Watson frustated by the lack of new cases, decide to turn their minds toward something interesting like solving few logical problems. One of the problems they have to solve now is as follows: Given an array A of size N and a list of Q number of queries, where each query has two numbers L and R, find for each query the number of inversions in the s