class bst_node(object):

    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.left_count = 0 # less than

# Name of this class is given by LeetCode, not my choice.
class Solution(object):

    def add_node(self, bst_pointer, new_node, position):
        if bst_pointer == None:
            return position, new_node
        if new_node.val < bst_pointer.val:
            bst_pointer.left_count += 1
            position, bst_pointer.left = self.add_node(bst_pointer.left, new_node, position)
        else:
            if new_node.val > bst_pointer.val:
                position += 1
            position += bst_pointer.left_count
            position, bst_pointer.right = self.add_node(bst_pointer.right, new_node, position)
        return position, bst_pointer

    # This method signature is also given by Leetcode.
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = []
        bst = None

        for n in nums[::-1]:
            smaller_after, bst = self.add_node(bst, bst_node(n), 0)
            res.append(smaller_after)

        return res[::-1]

# Few test cases ...
print(Solution().countSmaller([]))
print(Solution().countSmaller([5, 2, 6, 1]))