<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> import heapq <EOL> class DualHeap ( object ) : <EOL> def __init__ ( self ) : <EOL> """<STR_LIT>""" <EOL> self . min_h = [ ] <EOL> self . max_h = [ ] <EOL> def insert ( self , num ) : <EOL> if not self . min_h or num > self . min_h [ <NUM_LIT:0> ] : <EOL> heapq . heappush ( self . min_h , num ) <EOL> else : <EOL> heapq . heappush ( self . max_h , - num ) <EOL> self . balance ( ) <EOL> def balance ( self ) : <EOL> l1 = len ( self . min_h ) <EOL> l2 = len ( self . max_h ) <EOL> if l1 - l2 > <NUM_LIT:1> : <EOL> heapq . heappush ( self . max_h , - heapq . heappop ( self . min_h ) ) <EOL> self . balance ( ) <EOL> elif l2 - l1 > <NUM_LIT:1> : <EOL> heapq . heappush ( self . min_h , - heapq . heappop ( self . max_h ) ) <EOL> self . balance ( ) <EOL> return <EOL> def get_median ( self ) : <EOL> l1 = len ( self . min_h ) <EOL> l2 = len ( self . max_h ) <EOL> m = ( l1 + l2 - <NUM_LIT:1> ) / <NUM_LIT:2> <EOL> if ( l1 + l2 ) % <NUM_LIT:2> == <NUM_LIT:1> : <EOL> if m == l2 - <NUM_LIT:1> : <EOL> return - self . max_h [ <NUM_LIT:0> ] <EOL> elif m == l2 : <EOL> return self . min_h [ <NUM_LIT:0> ] <EOL> raise Exception ( "<STR_LIT>" ) <EOL> else : <EOL> return ( - self . max_h [ <NUM_LIT:0> ] + self . min_h [ <NUM_LIT:0> ] ) / <NUM_LIT> <EOL> class Solution : <EOL> def __init__ ( self ) : <EOL> self . dh = DualHeap ( ) <EOL> def solve ( self , cipher ) : <EOL> """<STR_LIT>""" <EOL> self . dh . insert ( cipher ) <EOL> return self . dh . get_median ( ) <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> import sys <EOL> f = open ( "<STR_LIT>" , "<STR_LIT:r>" ) <EOL> solution = Solution ( ) <EOL> testcases = int ( f . readline ( ) . strip ( ) ) <EOL> for t in xrange ( testcases ) : <EOL> cipher = int ( f . readline ( ) . strip ( ) ) <EOL> s = "<STR_LIT>" % ( solution . solve ( cipher ) ) <EOL> print s , </s>
