title: Given an array, find out the next smaller element for each element
body: <p>Given an array find the next smaller element in array for each element without changing the original order of the elements.</p>
  
  <p>For example, suppose the given array is 4,2,1,5,3. </p>
  
  <p>The resultant array would be 2,1,-1,3,-1.</p>
  
  <p>I was asked this question in an interview, but i couldn't think of a solution better than the trivial O(n^2) solution.
  Any approach that I could think of, i.e. making a binary search tree, or sorting the array, will distort the original order of the elements and hence lead to a  wrong result.</p>
  
  <p>Any help would be highly appreciated.</p>