Given an array A of distinct numbers, how to count the number of pairs `(i,j)`

such that

`A[i] < A[j]`

For example, let us consider `A = [2, 1, 3]`

the pairs are `(1,2), (1,3), (2,3)`

. So there are 3 pairs.

Similarly for `A = [10, 6, 9, 2]`

, there are 6 pairs

This problem was originally appeared in Codechef.

One straight forward solution is to loop through all possible pairs and count them.

But this has `O(n`

time complexity.^{2})

We actually don’t need to count all the pairs because the elements are distinct.

Suppose we arrange the elements in sorted order

`A = [1, 2, 3]`

then the pairs are `(1, 2), (1,3), (2,3)`

`A = [2, 6, 9, 10]`

the pairs are `(2, 6), (2,9), (2,10), (6, 9), (6, 10), (9,10)`

If there are n elements in an array, there will be` n*(n-1)`

pairs. Since the all the elements are unique, half of them satisfies the given property.

So the answer will be `n*(n-1)/2`