Given an array, find out the last smaller element for each element

We need to compute max(index) over all elements with smaller values.

Let's sort pairs (element, index) in lexicographical order and iterate over them keeping track of the largest index seen so far. That's exactly the position of the rightmost smaller element. Here's how one could implement it:

def get_right_smaller(xs):
    res = [-1] * len(xs)
    right_index = -1
    for val, idx in sorted((val, idx) for idx, val in enumerate(xs)):
        res[idx] = right_index if right_index > idx else -1
        right_index = max(right_index, idx)
    return res

This solution works properly even if the input array contains equal numbers because the element with smaller index goes earlier if the the values of two elements are the same.

The time complexity of this solution is O(N log N + N) = O(N log N) (it does sorting and one linear pass).

If all elements of the array are O(N), you can make this solution linear using count sort.

Make a list, add last element index. 
Walk through array right to left.     
For every element:
   if list tail value is smaller then current element
       find the most first smaller list element (binary search, list is sorted)
   otherwise 
       add element index to the list tail, output -1

for {4,2,1,5,3,6,2} example list will contain index 6 (value 2); index 2 (value 1)