<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class Solution ( object ) : <EOL> def solve ( self , cipher ) : <EOL> """<STR_LIT>""" <EOL> N , A = cipher <EOL> if N % <NUM_LIT:2> == <NUM_LIT:1> : <EOL> return self . find_kth ( A , <NUM_LIT:0> , N - <NUM_LIT:1> , ( N - <NUM_LIT:1> ) / <NUM_LIT:2> ) <EOL> else : <EOL> raise IndexError <EOL> def find_kth ( self , A , i , j , k ) : <EOL> """<STR_LIT>""" <EOL> p = self . partition ( A , i , j ) <EOL> if p == k : <EOL> return A [ p ] <EOL> if p > k : <EOL> return self . find_kth ( A , i , p - <NUM_LIT:1> , k ) <EOL> else : <EOL> return self . find_kth ( A , p + <NUM_LIT:1> , j , k ) <EOL> def partition ( self , A , i , j ) : <EOL> if i > j : <EOL> raise IndexError <EOL> if i == j : <EOL> return i <EOL> p = i <EOL> ptr_smaller = p <EOL> for ptr in xrange ( p + <NUM_LIT:1> , j + <NUM_LIT:1> ) : <EOL> if A [ ptr ] < A [ p ] : <EOL> ptr_smaller += <NUM_LIT:1> <EOL> A [ ptr ] , A [ ptr_smaller ] = A [ ptr_smaller ] , A [ ptr ] <EOL> A [ p ] , A [ ptr_smaller ] = A [ ptr_smaller ] , A [ p ] <EOL> return ptr_smaller <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> import sys <EOL> f = open ( "<STR_LIT>" , "<STR_LIT:r>" ) <EOL> solution = Solution ( ) <EOL> N = int ( f . readline ( ) . strip ( ) ) <EOL> A = map ( int , f . readline ( ) . strip ( ) . split ( '<STR_LIT:U+0020>' ) ) <EOL> cipher = N , A <EOL> s = "<STR_LIT>" % ( solution . solve ( cipher ) ) <EOL> print s , </s>
