title: given an array, for each element, find out the total number of elements lesser than it, which appear to the right of it
body: <p>I had previously posted a question, <a href="https://stackoverflow.com/questions/9493853/given-an-array-find-out-the-next-minimum-element-for-each-element">Given an array, find out the next smaller element for each element</a> 
  now, i was trying to know , if there is any way to find out "given an array, for each element, find out the total number of elements lesser than it, which appear to the right of it"
  for example, the array [4 2 1 5 3] should yield [3 1 0 1 0]??</p>
  
  <p>[EDIT]
  I have worked out a solution, please have a look at it, and let me know if there is any mistake.</p>
  
  <p>1 Make a balanced BST inserting elements traversing the array from right to left</p>
  
  <p>2 The BST is made in such a way that each element holds the size of the tree rooted at that element</p>
  
  <p>3 Now while you search for the right position to insert any element, take account of the total size of the subtree rooted at left sibling + 1(for parent) if you move right
  Now since, the count is being calculated at the time of insertion of an element, and that we are moving from right to left, we get the exact count of elements lesser than the given element appearing after it.</p>