<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class Node ( object ) : <EOL> def __init__ ( self , val ) : <EOL> """<STR_LIT>""" <EOL> self . val = val <EOL> self . cnt_left = <NUM_LIT:0> <EOL> self . cnt_this = <NUM_LIT:0> <EOL> self . left , self . right = None , None <EOL> def __repr__ ( self ) : <EOL> return repr ( self . val ) <EOL> class BST ( object ) : <EOL> def __init__ ( self ) : <EOL> self . root = None <EOL> def insert ( self , root , val ) : <EOL> """<STR_LIT>""" <EOL> if not root : <EOL> root = Node ( val ) <EOL> if root . val == val : <EOL> root . cnt_this += <NUM_LIT:1> <EOL> elif val < root . val : <EOL> root . cnt_left += <NUM_LIT:1> <EOL> root . left = self . insert ( root . left , val ) <EOL> else : <EOL> root . right = self . insert ( root . right , val ) <EOL> return root <EOL> def rank ( self , root , val ) : <EOL> """<STR_LIT>""" <EOL> if not root : <EOL> return <NUM_LIT:0> <EOL> if root . val < val : <EOL> return root . cnt_this + root . cnt_left + self . rank ( root . right , val ) <EOL> elif root . val == val : <EOL> return root . cnt_left <EOL> else : <EOL> return self . rank ( root . left , val ) <EOL> class Solution ( object ) : <EOL> def countOfSmallerNumberII ( self , A ) : <EOL> """<STR_LIT>""" <EOL> tree = BST ( ) <EOL> ret = [ ] <EOL> for a in A : <EOL> tree . root = tree . insert ( tree . root , a ) <EOL> ret . append ( tree . rank ( tree . root , a ) ) <EOL> return ret <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> assert Solution ( ) . countOfSmallerNumberII ( <EOL> [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:100> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:5> , <NUM_LIT> , <NUM_LIT:7> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:32> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:2> , <NUM_LIT> , <EOL> <NUM_LIT:3> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:9> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:100> , <NUM_LIT> ] ) == [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:3> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:5> , <NUM_LIT:0> , <NUM_LIT:4> , <NUM_LIT:0> , <NUM_LIT:5> , <NUM_LIT:1> , <NUM_LIT:6> , <NUM_LIT:2> , <NUM_LIT:9> , <NUM_LIT:2> , <NUM_LIT> , <NUM_LIT:10> , <NUM_LIT> , <EOL> <NUM_LIT> , <NUM_LIT:16> , <NUM_LIT:7> , <NUM_LIT:16> , <NUM_LIT:7> , <NUM_LIT> , <NUM_LIT:2> , <NUM_LIT:0> , <NUM_LIT> , <NUM_LIT:1> , <NUM_LIT:20> , <NUM_LIT> , <NUM_LIT:15> , <NUM_LIT:4> , <NUM_LIT:6> , <NUM_LIT> , <EOL> <NUM_LIT:20> , <NUM_LIT:20> , <NUM_LIT:16> , <NUM_LIT> , <NUM_LIT> ] </s>
