Problem:
 Score: 400 points    Problem Statement  We have N integers A_1, A_2, ..., A_N .  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K -th number in that list?      Constraints   All values in input are integers.  2 \leq N \leq 2 \times 10^5  1 \leq K \leq \frac{N(N-1)}{2}  -10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)         Input  Input is given from Standard Input in the following format:  N  K  A_1  A_2  \dots  A_N       Output  Print the answer.        Sample Input 1 4 3
3 3 -4 -2      Sample Output 1 -6  There are six ways to form a pair. The products of those pairs are 9 , -12 , -6 , -12 , -6 , 8 .  Sorting those numbers in ascending order, we have -12 , -12 , -6 , -6 , 8 , 9 . The third number in this list is -6 .       Sample Input 2 10 40
5 4 3 2 -1 0 0 0 0 0      Sample Output 2 6       Sample Input 3 30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0      Sample Output 3 448283280358331064

Solution (Python):
def main():
    import numpy as np
    from bisect import bisect_left,bisect_right
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=np.array(A)
    A=np.sort(A)
    Ap=A[A>0]
    Az=A[A==0]
    Am=A[A<0]   
    lm,lz,lp=len(Am),len(Az),len(Ap)
    Am2=Am**2
    Ap2=Ap**2
    
    def cnt_product(x): 
        if x<0:
            X=np.searchsorted(Am,x//Ap,side='right')
            
            return X.sum()
        
        else:
            ans=lz*(n-lz)+lz*(lz-1)//2+lp*lm

            X=np.searchsorted(Ap,x//Ap,side='right')
            Xd=np.count_nonzero(Ap2<=x)

            Y=np.searchsorted(Am,(-x-1)//(-Am),side='right')
            Yd=np.count_nonzero(Am2<=x)
            
            ans+=(X.sum()-Xd+lm**2-Y.sum()-Yd)//2
            return ans

    left=-10**18
    right=10**18
    while right-left>1:
        mid=(left+right)//2
        if cnt_product(mid)<k:
            left=mid
        else:
            right=mid
    print(right)

if __name__=='__main__':
    main()

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def dominus(t):
    r = len(plus)-1
    ans = 0
    for m in minus:
        while r>=0 and m*plus[r] >= -t:
            r -= 1
            if r<0:
                break
        ans += len(plus)-r-1
        
    
    return ans

def doplus(t):
    return doplus1(t,plus)+doplus1(t,minus)

def doplus1(t,b):
    ans = 0
    r = 0
    for i in range(len(b)-1,0,-1):
        p = b[i]
        r = min(r,i-1)
        while p*b[r] <= t:
            r += 1
            if r>=i:
                break
        ans += r
    
    return ans

n,k = inm()
a = inl()
plus = []
minus = []
nzero = 0
for x in a:
    if x<0:
        minus.append(-x)
    elif x>0:
        plus.append(x)
    else:
        nzero += 1
minus.sort()
plus.sort()
kminus = len(plus)*len(minus)
kzero = (2*n-1-nzero)*nzero//2
kmz = kminus+kzero
ddprint("n {} k {}".format(n,k))
ddprint("minus")
ddprint(minus)
ddprint(plus)
if kminus<k<=kminus+kzero:
    print(0)
else:
    dom = (kminus>=k)
    if not dom:
        mn = 0
        mx = 10**19
        while mx>mn+1:
            mid = (mx+mn)//2
            v = doplus(mid)
            if v>=k-kmz:
                mx = mid
            else:
                mn = mid
            
    else:
        mx = 0
        mn = -10**19
        while mx>mn+1:
            mid = (mx+mn)//2
            v = dominus(mid)
            if v>=k:
                mx = mid
            else:
                mn = mid
            
    print(mx)

Solution (Python):
import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a) 

a = np.sort(a)
zero = np.count_nonzero(a == 0) 
pos = a[a > 0] 
neg = a[a < 0] 

def count(x): 
    ans = 0
    if x >= 0: 
        ans += zero * n 
    ans += np.searchsorted(a, x // pos, side="right").sum()
    ans += n * len(neg) - np.searchsorted(a, -(-x // neg), side="left").sum()
    ans -= np.count_nonzero(a * a <= x) 
    return ans // 2

ok = 10 ** 18
ng = -ok - 1
while ok - ng > 1: 
    cen = (ok + ng) // 2
    if count(cen) >= k:
        ok = cen
    else:
        ng = cen
print(ok)

Solution (Python):
N, K = map(int, input().split())
plus = []
minus = []
zero = 0
for i in map(int, input().split()):
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zero += 1
plus.sort()
minus.sort(reverse=True)


def solve(mid):
    global N, K, zero
    cnt = 0
    if mid >= 0:
        cnt += len(plus) * len(minus)
        if mid > 0:
            cnt += zero * (zero - 1) // 2 + zero * (N - zero)
            for L in (plus, minus):
                l, r = 0, len(L) - 1
                while l < r:
                    while l < r and L[l] * L[r] >= mid:
                        r -= 1
                    cnt += r - l
                    l += 1
    else:
        r = len(minus) - 1
        for l in range(len(plus)):
            while r >= 0 and plus[l] * minus[r] < mid:
                r -= 1
            cnt += len(minus) - (r + 1)
    return cnt < K





ok, ng = -10 ** 19, 10 ** 19
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Solution (Python):
import numpy as np

n,k=map(int,input().split())
A=np.array(input().split(),np.int64)
A.sort()

zero=A[A==0]
neg=A[A<0]
pos=A[A>0]

def f(x): 
    cnt=0
    
    if x>=0:
        cnt += len(zero)*n
    
    cnt += A.searchsorted(x//pos,side="right").sum()
    
    cnt += (n-A.searchsorted(-(-x//neg),side="left")).sum()
    
    cnt-=np.count_nonzero(A*A<=x)
    return cnt//2

l=-10**18
r=10**18

while l<r:
    pov=(l+r)//2
    if f(pov)>=k:
        r=pov
    else:
        l=pov+1
print(l)

Solution (Python):
N, K, *A = map(int, open(0).read().split())

neg = sorted([-a for a in A if a < 0])
pos = sorted([a for a in A if a >= 0])

def _count_pair_neg(x):
    x = -x
    res = 0

    MAX = len(pos)
    i = 0
    for n in reversed(neg):
        while i < MAX and n * pos[i] < x:
            i += 1
            
        res += MAX - i
    return res


def _count_pair_pos(x):
    res = 0

    
    i = 0
    MAX = len(neg)
    for n in reversed(neg):
        if n * n <= x:
            res -= 1
            
        while i < MAX and neg[i] * n <= x:
            i += 1
        res += i
        
    
    i = 0
    MAX = len(pos)
    for n in reversed(pos):
        if n * n <= x:
            res -= 1
            
        while i < MAX and pos[i] * n <= x:
            i += 1
        res += i
        
    
    res //= 2
    res += len(neg) * len(pos)
    return res


def count_pair(x):
    if x < 0:
        return _count_pair_neg(x)
    
    return _count_pair_pos(x)



lb = 0
ub = 2 * 10 ** 18 + 2

while ub - lb > 1:
    mid = (ub + lb) // 2
    if count_pair(mid - 10 ** 18 - 1) < K:
        lb = mid
    else:
        ub = mid

print(ub - 10 ** 18 - 1)

Solution (Python):



n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0
for i in range(n):
  if arr[i]<0:
    nc+=1
  elif arr[i]==0:
    zc+=1
  else:
    pc+=1
ncc=nc*pc
zcc=zc*(nc+pc)+(zc*(zc-1))//2
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2
if k<=ncc:
  arr1=[]
  arr2=[]
  for i in range(n):
    if arr[i]<0:
      arr1.append(-arr[i])
    elif arr[i]>0:
      arr2.append(arr[i])
  arr1=arr1[::-1]
  c1=len(arr1)
  c2=len(arr2)
  l=0
  r=10**18+1
  k=ncc-k
  while r-l!=1:
    mid=(l+r)//2
    cnt=0
    pos=c2-1
    for i in range(c1):
      while pos!=-1:
        if arr2[pos]>mid//arr1[i]:
          pos-=1
        else:
          break        
      cnt+=pos+1
    if cnt>k:
      r=mid
    else:
      l=mid
  print(-r)
elif k<=(ncc+zcc):
  print(0)
else:
  arr1=[]
  arr2=[]
  for i in range(n):
    if arr[i]<0:
      arr1.append(-arr[i])
    elif arr[i]>0:
      arr2.append(arr[i])
  arr1=arr1[::-1]
  c1=len(arr1)
  c2=len(arr2)
  l=0
  r=10**18+1
  k-=(ncc+zcc)
  while r-l!=1:
    mid=(l+r)//2
    cnt1=0
    pos1=c1-1
    for i in range(c1):
      tmp=0
      while pos1!=-1:
        if arr1[pos1]>mid//arr1[i]:
          pos1-=1
        else:
          break
      tmp+=pos1+1
      if arr1[i]**2<mid:
        tmp-=1
      cnt1+=tmp
    cnt1=cnt1//2
    cnt2=0
    pos2=c2-1
    for i in range(c2):
      tmp=0
      while pos2!=-1:
        if arr2[pos2]>mid//arr2[i]:
          pos2-=1
        else:
          break
      tmp+=pos2+1
      if arr2[i]**2<mid:
        tmp-=1
      cnt2+=tmp
    cnt2=cnt2//2
    cnt=cnt1+cnt2
    if cnt>=k:
      r=mid
    else:
      l=mid
  print(r)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr())
A.sort()
pos = A[A>0]
zero = A[A==0]
neg = A[A<0]

def check(x):
    
    count = 0 
    if x >= 0:
        count += len(zero) * N
    count += (np.searchsorted(A, x//pos, side='right')).sum()
    count += (N - np.searchsorted(A, (-x-1)//(-neg), side='right')).sum()
    count -= np.count_nonzero(A * A <= x) 
    assert count % 2 == 0
    count //= 2
    return count >= K

left = - 10 ** 19 
right = 10 ** 19 
while right > left + 1:
    mid = (left+right) // 2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)

Solution (Python):
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=sorted(map(int,input().split()))

M=[]
Z=[]
P=[]

for a in A:
    if a<0:
        M.append(-a)
    elif a==0:
        Z.append(a)
    else:
        P.append(a)

M.reverse()

MINUS=len(M)*len(P)
PLUS=len(P)*(len(P)-1)//2+len(M)*(len(M)-1)//2
ZERO=N*(N-1)//2-PLUS-MINUS

if MINUS<K and K<=MINUS+ZERO:
    print(0)
    sys.exit()

if K<=MINUS:
    OK=10**18
    NG=0

    while OK-NG>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(M)):
            while NOW>=0 and mid<M[i]*P[NOW]:
                NOW-=1
            ANS+=len(P)-NOW-1

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(-OK)

else:
    OK=0
    NG=10**18
    K-=MINUS+ZERO

    while NG-OK>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(P)):
            while NOW>0 and mid<=P[i]*P[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        NOW=len(M)-1

        for i in range(len(M)):
            while NOW>0 and mid<=M[i]*M[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(OK)

Solution (Python):
import numpy as np
import sys
from collections import deque

n,k=list(map(int,input().strip().split(" ")))
a=np.sort(np.array(list(map(int,input().split(" ")))))

zero=len(a[a==0])
pos=a[a>0]
neg=a[a<0]

l,r=10**18,-10**18
while l-r>1:
    c=(r+l)//2
    cnt=0
    if c>=0:
        cnt+=n*zero
    
    cnt+=np.searchsorted(a,c//pos,side='right').sum()+(n-np.searchsorted(a,(-c-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=c)
    cnt//=2

    if cnt>=k:
        l=c
    else:
        r=c

print(l)

Solution (Python):
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a)
a.sort()
nega=a[a<0]
zera=a[a==0]
posa=a[a>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  y+=np.searchsorted(a,x//posa,side="right").sum()
  y+=n*len(nega)-np.searchsorted(a,-(-x//nega)).sum() 
  y-=len(a[a*a<=x])
  return y//2

r=10**18
l=-r-1
while r-l>1:
  c=(r+l)//2
  if cnt(c)>=k:
    r=c
  else:
    l=c
print(r)

Solution (Python):
import numpy as np

n, k = map(int, input().split())

A = np.array(input().split(), np.int64)

A.sort()

posA = A[A > 0]
negA = A[A < 0]
zeros = (A == 0).sum()

left = -10 ** 18
right = 10 ** 18

while left + 1 < right:
    num = (left + right) // 2

    less_count = 0

    if num >= 0:
        less_count += zeros * n

    limit_pair_for_pos = num // posA
    limit_idxs = np.searchsorted(A, limit_pair_for_pos, side='right')
    less_count += limit_idxs.sum()

    limit_pair_for_neg = -(-num // negA)
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='left')
    less_count += limit_idxs.sum()

    duplicate_cases = (A ** 2 <= num).sum()
    less_count -= duplicate_cases
    less_count //= 2

    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Solution (Python):
import numpy as np

n, k = map(int, input().split())

A = np.array(input().split(), np.int64)

A.sort()

posA = A[A > 0]
negA = A[A < 0]
zeros = (A == 0).sum()

left = -10 ** 18
right = 10 ** 18

while left + 1 < right:
    num = (left + right) // 2

    less_count = 0

    if num >= 0:
        less_count += zeros * n

    limit_pair_for_pos = num // posA
    limit_idxs = np.searchsorted(A, limit_pair_for_pos, side='right')
    less_count += limit_idxs.sum()

    limit_pair_for_neg = num // negA + (num % negA != 0)
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='left')
    less_count += limit_idxs.sum()

    duplicate_cases = (A ** 2 <= num).sum()
    less_count -= duplicate_cases
    less_count //= 2

    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Solution (Python):
import numpy as np

n, k = map(int, input().split())

A = np.array(input().split(), np.int64)

A.sort()

posA = A[A > 0]
negA = A[A < 0]
zeros = (A==0).sum()

left = -10**18
right = 10**18

while left+1 < right:
    num = (left+right)//2
    
    less_count = 0
    
    if num >= 0:
        less_count += zeros * n
    
    limit_pair_for_pos = num // posA
    limit_idxs = np.searchsorted(A, limit_pair_for_pos, side='right')
    less_count += limit_idxs.sum()

    limit_pair_for_neg = (num+negA+1) // negA
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='left')
    less_count += limit_idxs.sum()

    duplicate_cases = (A**2 <= num).sum()
    less_count -= duplicate_cases
    less_count //= 2
    
    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
A.sort()
plus = 0
minus = 0
zero = 0
plus_lis = []
minus_lis = []

for n in A:
	if n == 0:
		zero += 1
	elif n > 0:
		plus += 1
		plus_lis.append(n)
	else:
		minus += 1
		minus_lis.append(n)

plus, minus, zero = plus*(plus-1)//2+minus*(minus-1)//2, plus*minus, plus*zero+minus*zero+zero*(zero-1)//2

if K <= minus:  
	l = -10**18-1
	r = 0

	def count(x):  
		total = 0
		idx = 0
		for i in range(len(plus_lis)):
			while idx < len(minus_lis):
				if plus_lis[i] * minus_lis[idx] < x:
					idx += 1
				else:
					total += idx
					break
			else:
				total += idx

		return total

	while l+1 != r:
		m = (l+r)//2
		if count(m) >= K:
			r = m
		else:
			l = m
	print(l)

elif minus <= K <= minus+zero:
	print(0)

else:  
	l = 0
	r = 10**18+1

	def count(x):  
		total = minus+zero
		tmp = 0
		idx = 0

		
		for i in range(len(plus_lis))[::-1]:
			while idx < len(plus_lis):
				if plus_lis[i] * plus_lis[idx] < x:
					idx += 1
				else:
					tmp += idx
					break
			else:
				tmp += idx
			if plus_lis[i] * plus_lis[i] < x: tmp -= 1  
		tmp //= 2
		total += tmp
		tmp = 0
		idx = 0 
		for i in range(len(minus_lis)):
			while idx < len(minus_lis):
				if minus_lis[i] * minus_lis[-idx-1] < x:
					idx += 1
				else:
					tmp += idx
					break
			else:
				tmp += idx
			if minus_lis[i] * minus_lis[i] < x: tmp -= 1
		tmp //= 2
		total += tmp

		return total

	while l+1 != r:
		m = (l+r)//2
		if count(m) >= K:
			r = m
		else:
			l = m
	print(l)

Solution (Python):
def main():
    from bisect import bisect_left as bl

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()

    inf = 10**18+1

    ok = -inf
    ng = inf
    start_0 = bl(a, 0)
    start_1 = bl(a, 1)

    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        if mid >= 0:
            now = 0
            if start_0 > 0:
                for i in a[start_0-1::-1]:
                    while now < n:
                        if i*a[now] >= mid:
                            now += 1
                        else:
                            break
                    cnt += n - now
            now = n
            for i in a[start_1:]:
                while now > 0:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        else:
            now = 0
            for i in a[:start_0]:
                while now < n:
                    if i*a[now] >= mid:
                        now += 1
                    else:
                        break
                cnt += n - now
            now = n
            for i in a[n-1:start_1-1:-1]:
                while now > 0:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        if mid > 0:
            cnt += n * (start_1 - start_0)
        cnt -= len([None for i in a if i*i < mid])
        if cnt//2 < k:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Solution (Python):
N,K = map(int,input().split())
plst = []
nlst = []
p = 0
z = 0
n = 0
for i in map(int,input().split()):
    if i > 0:
        p += 1
        plst.append(i)
    elif i == 0:
        z += 1
    else:
        n += 1
        nlst.append(i)
plst.sort()
nlst.sort()
zp = (p+n)*z + z*(z-1)//2
np = p*n
if K <= np:
    l = -10**18-1
    r = 0
    while l+1 < r:
        m = (l+r)//2
        total = 0
        idx = 0
        for i in range(p):
            while idx < n:
                if plst[i] * nlst[idx] < m:
                    idx += 1
                else:
                    total += idx
                    break
            else:
                total += idx
        if total < K:
            l = m
        else:
            r = m
    ans = l
elif K <= np+zp:
    ans = 0
else:
    l = 0
    r = 10**18+1
    while l+1 < r:
        m = (l+r)//2
        total = np+zp
        tmp = 0
        idx = 0
        for i in range(p)[::-1]:
            while idx < p:
                if plst[i] * plst[idx] < m:
                    idx += 1
                else:
                    tmp += idx
                    break
            else:
                tmp += idx
            if plst[i] * plst[i] < m: tmp -= 1
        tmp //= 2
        total += tmp
        tmp = 0
        idx = 0 
        for i in range(n):
            while idx < n:
                if nlst[i] * nlst[-idx-1] < m:
                    idx += 1
                else:
                    tmp += idx
                    break
            else:
                tmp += idx
            if nlst[i] * nlst[i] < m: tmp -= 1
        tmp //= 2
        total += tmp
        if total < K:
            l = m      
        else:
            r = m
    ans = l
print(ans)

Solution (Python):
import numpy as np
N,K = map(int,input().split())
A = np.array([int(i) for i in input().split()])


A = np.sort(A)
posi = A[A>0]
zero = A[A==0]
nega = A[A<0]

def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    
    if x >= 0:
        cnt_tpl += len(zero) * N
    
    cnt_tpl += np.searchsorted(A, x//posi, side='right').sum()
    
    cnt_tpl += (N - np.searchsorted(A, (-x - 1) // (-nega), side='right')).sum()
    
    cnt_tpl -= np.count_nonzero(A*A <= x)
    return cnt_tpl // 2


left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x

print(right)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = max(A[-1]**2+10,A[0]**2+10)
l = A[0]*A[-1]-10
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    cou=0
    for i in range(0,plu):
      while True:
        if cou>=plu-i-1:
          num+=plu-i-1
          break
        x = A_plu_rev[i]*A_plu[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r=m
      continue
    cou = 0
    for i in range(0,mi):
      while True:
        if cou>=mi-i-1:
          num+=mi-i-1
          break
        x = A_mi[i]*A_mi_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break

    if num>=K:
      r=m
    else:
      l=m
    
  elif m==0:
    num+=num_mi
    if num>=K:
      r=m
    else:
      l=m
  else:
    cou = 0
    for a in A_mi_rev:
      while True:
        if cou==plu:
          num+=cou
          break
        x = a*A_plu_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r = m
    else:
      l = m
      
print(l)

Solution (Python):
from bisect import bisect


def check_neg(m, k, pos, neg, len_pos):
    less = 0  
    j = 0
    for a in neg:
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if len_pos == j:
            break
        less += len_pos - j
    return less < k


def check_pos(m, k, pos, neg, len_pos, len_neg):
    less_eq = 0  
    j = 0
    for i in range(len_pos - 1, -1, -1):
        a = pos[i]
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if j == len_pos:
            less_eq += len_pos * (i + 1)
            break
        less_eq += j

    j = 0
    for i in range(len_neg - 1, -1, -1):
        a = neg[i]
        d = m // a
        while j < len_neg and neg[j] <= d:
            j += 1
        if j == len_neg:
            less_eq += len_neg * (i + 1)
            break
        less_eq += j

    m_sqrt = int(m ** 0.5)
    less_eq -= bisect(pos, m_sqrt)
    less_eq -= bisect(neg, m_sqrt)

    less_eq //= 2

    return less_eq < k


def solve(n, k, aaa):
    pos = [a for a in aaa if a > 0]
    neg = [a for a in aaa if a < 0]
    len_pos = len(pos)
    len_neg = len(neg)
    neg_mul = len_pos * len_neg
    pos_mul = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
    if neg_mul >= k:
        l = -(10 ** 18)
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg, len_pos):
                l = m
            else:
                r = m
        return l
    elif n * (n - 1) // 2 - pos_mul >= k:
        return 0
    else:
        k -= n * (n - 1) // 2 - pos_mul
        l = 0
        r = 10 ** 18
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg, len_pos, len_neg):
                l = m
            else:
                r = m
        return r


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(n, k, aaa))


def debug():
    mul = []
    for i in range(n):
        for j in range(i + 1, n):
            mul.append(aaa[i] * aaa[j])
    mul.sort()
    print(mul[k - 1], mul)

Solution (Python):
import numpy as np

n, k = map(int, input().split())
num_list = [int(i) for i in input().split()]
num_list = np.array(num_list)
num_list.sort()

neg = num_list[num_list < 0]
pos = num_list[num_list > 0]
zero =  num_list[num_list == 0]

def count(x):
    ans = 0
    if x >= 0:
        ans += len(zero) * n
    ans += np.searchsorted(num_list, x // pos, side="right").sum()
    ans += n * len(neg) - np.searchsorted(num_list, -(-x // neg), side="left").sum()
    ans -= np.count_nonzero(num_list * num_list <= x)
    return ans // 2

left = -(10 ** 18)
right = 10 ** 18

while left + 1 < right:
    mid = (left + right) // 2
    if count(mid) >= k:
        right = mid
    else:
        left = mid

print(right)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
mA, nA = [], []
for a in A:
    if a < 0:
        mA.append(a)
    else:
        nA.append(a)
mA = sorted(mA)[::-1]
nA = sorted(nA)
lnA = len(nA)
lmA = len(mA)


def F(k):
    
    
    r = 0
    i, j = 0, lnA-1
    while i < lnA:
        while j >= 0 and nA[j]*nA[i] > k:
            j -= 1
        r += j+1
        i += 1

    
    i, j = 0, lmA-1
    while i < lmA:
        while j >= 0 and mA[j]*mA[i] > k:
            j -= 1
        r += j+1
        i += 1

    
    i, j = 0, lmA-1
    while i < lnA:
        while j >= 0 and mA[j]*nA[i] <= k:
            j -= 1
        r += 2*(lmA-j-1)
        i += 1
    for a in A:
        if a*a <= k:
            r -= 1
    return r//2


mx, mn = 2*10**18, -2*10**18
idx = (mx+mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        mn = idx
    else:
        mx = idx
    idx = (mx+mn)//2
print(idx+1)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
mA, nA = [], []
for a in A:
    if a < 0:
        mA.append(a)
    else:
        nA.append(a)
mA = sorted(mA)[::-1]
nA = sorted(nA)
lnA = len(nA)
lmA = len(mA)


def F(k):
    
    
    r = 0
    i, j = 0, lnA-1
    while i < lnA:
        while j >= 0 and nA[j]*nA[i] > k:
            j -= 1
        r += j+1
        i += 1

    
    i, j = 0, lmA-1
    while i < lmA:
        while j >= 0 and mA[j]*mA[i] > k:
            j -= 1
        r += j+1
        i += 1

    






    i, j = lmA-1, 0
    while i >= 0:
        while j < lnA and nA[j]*mA[i] > idx:
            j += 1
        r += 2*(lnA-j)
        i -= 1
    for a in A:
        if a*a <= k:
            r -= 1
    return r//2


mx, mn = 2*10**18, -2*10**18
idx = (mx+mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        mn = idx
    else:
        mx = idx
    idx = (mx+mn)//2
print(idx+1)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
zeros = 0
for a in A:
    if a > 0:
        pos.append(a)
    elif a < 0:
        neg.append(a)
    else:
        zeros += 1

pos.sort()
neg.sort(reverse=True)

minus_pattern = len(pos) * len(neg)
zero_pattern = zeros * (len(pos)+len(neg)) + (zeros*(zeros-1))//2

pos_length = len(pos)
neg_length = len(neg)

left = -10**18
right = 10**18

while left + 1 < right:
    num = (left+right)//2
    less_count = 0

    if num >= 0:
        pos_idx = pos_length-1
        for p in pos:
            while pos_idx >= 0 and p * pos[pos_idx] > num:
                pos_idx -= 1
            less_count += pos_idx + 1
            if p**2 <= num:
                less_count -= 1

        neg_idx = neg_length-1
        for m in neg:
            while neg_idx >= 0 and m * neg[neg_idx] > num:
                neg_idx -= 1
            less_count += neg_idx + 1
            if m**2 <= num:
                less_count -= 1

        less_count //= 2
        less_count += minus_pattern + zero_pattern

    elif num < 0:
        pos_idx = 0
        for m in neg[::-1]:
            while pos_idx < pos_length and m * pos[pos_idx] > num:
                pos_idx += 1
            less_count += pos_length - pos_idx

    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
mA, nA = [], []
for a in A:
    if a<0:
        mA.append(a)
    else:
        nA.append(a)
lnA = len(nA)
lmA = len(mA)

def F(idx):
    i, j = 0, lnA-1
    r = 0
    while i < lnA:
        while j >= 0 and nA[j]*nA[i] > idx:
            j -= 1
        r += j+1
        i += 1
    i, j = lmA-1, 0
    while i >= 0:
        while j < lmA and mA[j]*mA[i] > idx:
            j += 1
        r += lmA-j
        i -= 1
    i, j = 0, 0
    while i < lmA:
        while j < lnA and nA[j]*mA[i] > idx:
            j += 1
        r += 2*(lnA-j)
        i += 1
    for a in A:
        if a*a <= idx:
            r-=1
    return r//2

mx, mn = 2*10**18, -2*10**18
idx = (mx + mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        idx, mn = (idx + mx)//2, idx
    else:
        idx, mx = (idx + mn)//2, idx
print(idx+1)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
mA, nA = [], []
dd = []
for a in A:
    if a<0:
        mA.append(a)
    else:
        nA.append(a)
    dd.append(a*a)


lnA = len(nA)
lmA = len(mA)

def F(idx):
    j = lnA-1
    r = 0
    for a in nA:
        while j >= 0:
            if nA[j]*a <= idx:
                break
            j -= 1
        r += j+1
    j = 0
    for a in mA[::-1]:
        while j < lmA:
            if mA[j]*a <= idx:
                break
            j += 1
        r += lmA-j
    j = 0
    for a in mA:
        while j < lnA:
            if nA[j]*a <= idx:
                break
            j += 1
        r += 2*(lnA-j)

    for a in dd:
        if a <= idx:
            r-=1
    return r//2


mx, mn = 2*10**18, -2*10**18
idx = (mx + mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        idx, mn = (idx + mx)//2, idx
        continue
    idx, mx = (idx + mn)//2, idx
print(idx+1)

Solution (Python):
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

N,K=map(int,input().split())
A=list(map(int,input().split()))

minas=[]
plus=[]
zero=[]
for a in A:
    if a<0:
        minas.append(-a)
    else:
        plus.append(a)
minas.sort()
plus.sort()

st=-(10**18)-1
ed=10**18+1
len_minas=len(minas)
len_plus=len(plus)
len_zero=len(zero)
zero1=len_plus*len_minas
zero2=len_zero*(len_minas+len_plus)+len_zero*(len_zero-1)//2



while ed-st>1:
    mid=(st+ed)//2
    if mid<0:
        j=0
        i=0
        for m in range(len(minas)-1,-1,-1):
            while i<len(plus) and plus[i]*minas[m]<-mid:
                i+=1
            j+=len(plus)-i
    else:
        j=zero1
        i=len(minas)-1
        for m in range(len(minas)-1):
            while m<i and minas[i]*minas[m]>mid:
                i-=1
            j+=max(i-m,0)


        i=len(plus)-1
        for m in range(len(plus)-1):
            while m<i and plus[i]*plus[m]>mid:
                i-=1
            j+=max(i-m,0)
    if j<K:
        st=mid
    else:
        ed=mid

print(ed)