I think that we simply need to calculate for every index j, how many indices i < j satisfy inequality a_i > a_j (lets denote result as A), how many indices k > j satisfy inequality a_j > a_k (lets denote result as B), and add to answer A·B. We can calculate A, adding numbers to BIT in decreasing order, and for calculating B we add numbers to another BIT in increasing order.

Let's use 2 BITs. First BIT T1[x] will count number of elements greater or equal than x, while second BIT T2[x] will count number of inversions i, j (i < j and A[i] > A[j]) such that A[j] >  = x, that is number of inversions with second element greater or equal to x. Then after reading a number n, we query the first bit for n + 1 and perform increase operation to the second BIT at n with that value. Finally we query second BIT for n + 1 and add that value to our final answer.

Code is very short and pretty -> C++ Code

There is a similar problem on CF:

http://codeforces.net/problemset/problem/61/E

Yet another similar problem.

You can use two segment tree for solving it in O(nlogn), for tracking the number of elements smaller to the right and larger to the left of any particular element then basically you have to add all the left[i]*right[i]