<s> """<STR_LIT>""" <EOL> from bisect import bisect_left , bisect_right <EOL> class SortedCollection ( object ) : <EOL> '''<STR_LIT>''' <EOL> def __init__ ( self , iterable = ( ) , key = None ) : <EOL> self . _given_key = key <EOL> key = ( lambda x : x ) if key is None else key <EOL> decorated = sorted ( ( key ( item ) , item ) for item in iterable ) <EOL> self . _keys = [ k for k , item in decorated ] <EOL> self . _items = [ item for k , item in decorated ] <EOL> self . _key = key <EOL> def _getkey ( self ) : <EOL> return self . _key <EOL> def _setkey ( self , key ) : <EOL> if key is not self . _key : <EOL> self . __init__ ( self . _items , key = key ) <EOL> def _delkey ( self ) : <EOL> self . _setkey ( None ) <EOL> key = property ( _getkey , _setkey , _delkey , '<STR_LIT>' ) <EOL> def clear ( self ) : <EOL> self . __init__ ( [ ] , self . _key ) <EOL> def copy ( self ) : <EOL> return self . __class__ ( self , self . _key ) <EOL> def __len__ ( self ) : <EOL> return len ( self . _items ) <EOL> def __getitem__ ( self , i ) : <EOL> return self . _items [ i ] <EOL> def __iter__ ( self ) : <EOL> return iter ( self . _items ) <EOL> def __reversed__ ( self ) : <EOL> return reversed ( self . _items ) <EOL> def __repr__ ( self ) : <EOL> return '<STR_LIT>' % ( <EOL> self . __class__ . __name__ , <EOL> self . _items , <EOL> getattr ( self . _given_key , '<STR_LIT>' , repr ( self . _given_key ) ) <EOL> ) <EOL> def __reduce__ ( self ) : <EOL> return self . __class__ , ( self . _items , self . _given_key ) <EOL> def __contains__ ( self , item ) : <EOL> k = self . _key ( item ) <EOL> i = bisect_left ( self . _keys , k ) <EOL> j = bisect_right ( self . _keys , k ) <EOL> return item in self . _items [ i : j ] <EOL> def index ( self , item ) : <EOL> '<STR_LIT>' <EOL> k = self . _key ( item ) <EOL> i = bisect_left ( self . _keys , k ) <EOL> j = bisect_right ( self . _keys , k ) <EOL> return self . _items [ i : j ] . index ( item ) + i <EOL> def count ( self , item ) : <EOL> '<STR_LIT>' <EOL> k = self . _key ( item ) <EOL> i = bisect_left ( self . _keys , k ) <EOL> j = bisect_right ( self . _keys , k ) <EOL> return self . _items [ i : j ] . count ( item ) <EOL> def insert ( self , item ) : <EOL> '<STR_LIT>' <EOL> k = self . _key ( item ) <EOL> i = bisect_left ( self . _keys , k ) <EOL> self . _keys . insert ( i , k ) <EOL> self . _items . insert ( i , item ) <EOL> def insert_right ( self , item ) : <EOL> '<STR_LIT>' <EOL> k = self . _key ( item ) <EOL> i = bisect_right ( self . _keys , k ) <EOL> self . _keys . insert ( i , k ) <EOL> self . _items . insert ( i , item ) <EOL> def remove ( self , item ) : <EOL> '<STR_LIT>' <EOL> i = self . index ( item ) <EOL> del self . _keys [ i ] <EOL> del self . _items [ i ] <EOL> def find ( self , k ) : <EOL> '<STR_LIT>' <EOL> i = bisect_left ( self . _keys , k ) <EOL> if i != len ( self ) and self . _keys [ i ] == k : <EOL> return self . _items [ i ] <EOL> raise ValueError ( '<STR_LIT>' % ( k , ) ) <EOL> def find_le ( self , k ) : <EOL> '<STR_LIT>' <EOL> i = bisect_right ( self . _keys , k ) <EOL> if i : <EOL> return self . _items [ i - <NUM_LIT:1> ] <EOL> raise ValueError ( '<STR_LIT>' % ( k , ) ) <EOL> def find_lt ( self , k ) : <EOL> '<STR_LIT>' <EOL> i = bisect_left ( self . _keys , k ) <EOL> if i : <EOL> return self . _items [ i - <NUM_LIT:1> ] <EOL> raise ValueError ( '<STR_LIT>' % ( k , ) ) <EOL> def find_ge ( self , k ) : <EOL> '<STR_LIT>' <EOL> i = bisect_left ( self . _keys , k ) <EOL> if i != len ( self ) : <EOL> return self . _items [ i ] <EOL> raise ValueError ( '<STR_LIT>' % ( k , ) ) <EOL> def find_gt ( self , k ) : <EOL> '<STR_LIT>' <EOL> i = bisect_right ( self . _keys , k ) <EOL> if i != len ( self ) : <EOL> return self . _items [ i ] <EOL> raise ValueError ( '<STR_LIT>' % ( k , ) ) </s>
