This one can be solved in O(nlgn) using a segment tree.

First we convert all powers to numbers in range 0..n-1 to avoid working with segments as large as 10

^{9}in our segment tree. Then for each of the men we should find number of men who are placed before him and have more power let's call this gr[j]. When ever we reach a man with power x we add the segment [0,x-1] to our segment tree , so finding gr[j] can be done by querying power of j in our segment tree when it's updated by all j-1 preceding men.Now let's call number of men who are standing after j but are weaker than j as le[j]. These values can be found using the same method with a segment-tree or in O(n) time using direct arithmetic:

le[j]=(power of j -1)-(i-1-gr[j])

note that powers are in range 0..n-1 now.

Now we can count all triplets i,j,k which have j as their second index. This is le[j]*gr[j]

so the final answer is

( \sum_{j=0}^{n-1} le[j]\times gr[j] )

Is implementation of segement tree really tough?

Thanx.

It more or less look like "familiar" Binary Search.

BIT?Can this be done using merge sort ...

like inverse counting problem?

Yes. For each index i, you can first find number of all inversions that have i as their first element and then all those that have i as their second element. Then just multiply them to find number of three-inversions (j,i,k) with i as their middle element.

What is the meaning of this line "we add the segment [0,x-1] to our segment tree".

An example would be very helpful.

my solution using merge sort algo to find inversions. http://codeforces.com/contest/61/submission/33820916

For the second time of inversion counting, I got the gist of what you are doing, namely, finding for each element, the number of inversions in which it is occurring as the first element. Please can you elaborate more on the thought process behind the processing you have done before you invoke the inversion count the second time?