# your code goes here
def orderStat( A, l, r, K) :
k = K - 1
#if l == r:
# return A[l]
if r - l <= 25 :
order5( A, l, r)
print ( A[ k] )
return ( A[ k] )
m = ( r - l) //5 + 1
#test
print ( 'm is' , m)
#
B = [ ]
for i in range ( m) :
B[ i] = orderStat( A, 5 *i, min ( 5 *i+4 , len ( A) -1 ) , 3 )
mom = orderStat( B, 0 , len ( B) -1 , len ( B) //2 )
p = partition( A, l, r)
pl = p - l + 1
if k < pl:
return orderStat( A, l, p-1 , K)
elif k > pl:
return orderStat( A, p+1 , r, K - p -1 )
else :
return mom
pass
def partition( A, l, r) :
x = A[ l]
i = l
for j in range ( l+1 , r) :
if A[ j] <= x:
i += 1
A[ i] , A[ j] = A[ j] , A[ i]
A[ i] , A[ l] = A[ l] , A[ i]
return i
pass
# Return the approximate median among elements A[l ... r]
def approxMed( A, l, r) :
pass
# Rearrange A[start, start+1, ..., min(start+4, len(A)-1)] in ascending order
def order5( A, start, stop) :
i = start+1
for i in range ( start+1 , min ( stop+1 , len ( A) ) ) :
j = i
while start+1 <= j and A[ j-1 ] > A[ j] :
A[ j-1 ] , A[ j] = A[ j] , A[ j-1 ]
j -= 1
list = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 14 , 15 , 16 , 18 , 19 , 20 , 22 , 26 , 28 , 29 , 30 , 37 , 38 , 39 , 50 , 52 , 127 , 46 , 48 ]
#result = order5(list, 0, len(list)-1)
result = orderStat( list , 0 , len ( list ) -1 , 5 )
print ( result)
IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmRlZiBvcmRlclN0YXQoQSwgbCwgciwgSyk6CiAgICBrID0gSyAtIDEKICAgICNpZiBsID09IHI6CiAgICAjICAgIHJldHVybiBBW2xdCiAgICBpZiByIC0gbCA8PSAyNToKICAgICAgICBvcmRlcjUoQSwgbCwgcikKICAgICAgICBwcmludChBW2tdKQogICAgICAgIHJldHVybihBW2tdKQogICAgbSA9IChyIC0gbCkvLzUgKyAxCiAgICAjdGVzdAogICAgcHJpbnQoJ20gaXMnLCBtKQogICAgIwogICAgQiA9IFtdCiAgICBmb3IgaSBpbiByYW5nZShtKToKICAgICAgICBCW2ldID0gb3JkZXJTdGF0KEEsIDUqaSwgbWluKDUqaSs0LGxlbihBKS0xKSwgMykKICAgIG1vbSA9IG9yZGVyU3RhdChCLCAwLCBsZW4oQiktMSwgbGVuKEIpLy8yKQogCiAgICBwID0gcGFydGl0aW9uKEEsIGwsIHIpCiAgICBwbCA9IHAgLSBsICsgMQogCiAgICBpZiBrIDwgcGw6CiAgICAgICAgcmV0dXJuIG9yZGVyU3RhdChBLCBsLCBwLTEsIEspCiAgICBlbGlmIGsgPiBwbDoKICAgICAgICByZXR1cm4gb3JkZXJTdGF0KEEsIHArMSwgciwgSyAtIHAgLTEpICAgICAKICAgIGVsc2U6CiAgICAgICAgcmV0dXJuIG1vbQogICAgcGFzcwogCmRlZiBwYXJ0aXRpb24oQSwgbCwgcik6CiAgICB4ID0gQVtsXQogICAgaSA9IGwKICAgIGZvciBqIGluIHJhbmdlKGwrMSwgcik6CiAgICAgICAgaWYgQVtqXSA8PSB4OgogICAgICAgICAgICBpICs9IDEKICAgICAgICAgICAgQVtpXSxBW2pdID0gQVtqXSxBW2ldCiAgICBBW2ldLEFbbF0gPSBBW2xdLEFbaV0KIAogICAgcmV0dXJuIGkKIAogICAgcGFzcwojIFJldHVybiB0aGUgYXBwcm94aW1hdGUgbWVkaWFuIGFtb25nIGVsZW1lbnRzIEFbbCAuLi4gcl0KZGVmIGFwcHJveE1lZChBLCBsLCByKToKICAgIHBhc3MKIAojIFJlYXJyYW5nZSBBW3N0YXJ0LCBzdGFydCsxLCAuLi4sIG1pbihzdGFydCs0LCBsZW4oQSktMSldIGluIGFzY2VuZGluZyBvcmRlcgpkZWYgb3JkZXI1KEEsIHN0YXJ0LCBzdG9wKToKICAgIGkgPSBzdGFydCsxCiAgICBmb3IgaSBpbiByYW5nZShzdGFydCsxLCBtaW4oc3RvcCsxLCBsZW4oQSkpKToKICAgICAgICBqID0gaQogICAgICAgIHdoaWxlIHN0YXJ0KzE8PWogYW5kIEFbai0xXT5BW2pdOgogICAgICAgICAgICBBW2otMV0sQVtqXSA9IEFbal0sQVtqLTFdCiAgICAgICAgICAgIGogLT0gMQogCmxpc3QgPSBbMSwyLDMsNCw1LDYsNyw4LDksMTAsMTEsMTQsMTUsMTYsMTgsMTksMjAsMjIsMjYsMjgsMjksMzAsMzcsMzgsMzksNTAsNTIsMTI3LDQ2LDQ4XQojcmVzdWx0ID0gb3JkZXI1KGxpc3QsIDAsIGxlbihsaXN0KS0xKQpyZXN1bHQgPSBvcmRlclN0YXQobGlzdCwgMCwgbGVuKGxpc3QpLTEsIDUpCnByaW50KHJlc3VsdCk=