import random
import time
 
def median5(a): #find median size<=5
	n=len(a)
	return sorted(a)[n//2]
 
 
def kth(a,k):
    if k==1:
        return min(a)
    n=len(a)
 
    median=[]
    i=0
    while i<n//5:
    	median.append(median5(a[i*5:i*5+5]))
    	i+=1
    if n%5:
    	median.append(median5(a[i*5:]))
 
    if len(median)==1:
    	pivot=a[0]
    else:
    	pivot=kth(median,len(median)//2)
 
    less=filter(lambda x:x<pivot,a)
    nEq=a.count(pivot)
    greater=filter(lambda x:x>pivot,a)
    nL=len(less)
    nG=len(greater)
    if  k<=nL:
        return kth(less,k)
    elif k<=nL+nEq:
        return pivot
    return kth(greater,k-nL-nEq)
 
 
 
n=1000000
a=[]
for i in range(n):
    a.append(random.randint(0,n))
 
k=random.randint(1,n)
print kth(a,k),sorted(a[:])[k-1]
 

aW1wb3J0IHJhbmRvbQppbXBvcnQgdGltZQoKZGVmIG1lZGlhbjUoYSk6ICNmaW5kIG1lZGlhbiBzaXplPD01CgluPWxlbihhKQoJcmV0dXJuIHNvcnRlZChhKVtuLy8yXQoKCmRlZiBrdGgoYSxrKToKICAgIGlmIGs9PTE6CiAgICAgICAgcmV0dXJuIG1pbihhKQogICAgbj1sZW4oYSkKICAgCiAgICBtZWRpYW49W10KICAgIGk9MAogICAgd2hpbGUgaTxuLy81OgogICAgCW1lZGlhbi5hcHBlbmQobWVkaWFuNShhW2kqNTppKjUrNV0pKQogICAgCWkrPTEKICAgIGlmIG4lNToKICAgIAltZWRpYW4uYXBwZW5kKG1lZGlhbjUoYVtpKjU6XSkpCiAgICAKICAgIGlmIGxlbihtZWRpYW4pPT0xOgogICAgCXBpdm90PWFbMF0KICAgIGVsc2U6CiAgICAJcGl2b3Q9a3RoKG1lZGlhbixsZW4obWVkaWFuKS8vMikKICAgIAogICAgbGVzcz1maWx0ZXIobGFtYmRhIHg6eDxwaXZvdCxhKQogICAgbkVxPWEuY291bnQocGl2b3QpCiAgICBncmVhdGVyPWZpbHRlcihsYW1iZGEgeDp4PnBpdm90LGEpCiAgICBuTD1sZW4obGVzcykKICAgIG5HPWxlbihncmVhdGVyKQogICAgaWYgIGs8PW5MOgogICAgICAgIHJldHVybiBrdGgobGVzcyxrKQogICAgZWxpZiBrPD1uTCtuRXE6CiAgICAgICAgcmV0dXJuIHBpdm90CiAgICByZXR1cm4ga3RoKGdyZWF0ZXIsay1uTC1uRXEpCgoKCm49MTAwMDAwMAphPVtdCmZvciBpIGluIHJhbmdlKG4pOgogICAgYS5hcHBlbmQocmFuZG9tLnJhbmRpbnQoMCxuKSkKCms9cmFuZG9tLnJhbmRpbnQoMSxuKQpwcmludCBrdGgoYSxrKSxzb3J0ZWQoYVs6XSlbay0xXQo=