트리구조를 사용하시면 될 것 같네요
5 1 3 0 2 4 가 있으면 오른쪽에서 부터 트리를 만듭니다.
만들 때, 자식이 왼쪽으로 갈 때마다 부모노드의 값을 +1을 해줍니다(자기보다 왼쪽에 있는, 자기보다 작은 값들의 수). 그러다가 자식이 오른쪽으로 가게 되면, 그 노드는 부모의 노드에 저장된 값 + 1(부모가 자기보다 작으므로) 만큼 자기 오른쪽에 자기보다 작은 원소를 갖고 있습니다.
 4 ->        4 (1)           ->             4(2)             ->                  4(3)                        ->            4(4)         ->      4(4)
            2                             2 (1)                                   2(1)                                        2(2)                   (생략)    5:(0, 4+1) 개
                                         0                                      0          3 : (0, (1 + 1 개))         0(0)    3 
                                                                                                                                         1(0+1)

http://stackoverflow.com/questions/9495843/given-a...

이 링크를 참조하시면 구현도 나와있네요