Sum of elements in unsorted array

 Given an unsorted array.
 With each number, we can associated a sum which is equal to the sum of all the numbers, less than the   current number.
  We've to find the total sum of all those numbers.
  e.g. unsorted array :1, 5, 3, 6, 4.
  for a[0]=1, sum[0]=0
  for a[1]=5, sum[1]=1
  for a[2]=3, sum[2]=1
  for a[3]=6, sum[3]=1+5+3
  for a[4]=4, sum[4]=1+3
  total sum =sum[0]+sum[1]+sum[2]+sum[3]+sum[4] = 15

Solution:
Read each element in the array and put it into a Binary Search Tree. Each node of the BST will hold the value of the element,  and also the sum of the left subtree. As the elements are inserted, calculate the sum of the left subtree. At the end of inserting all the elements, the total sum is calculated