Harryxun/stf_run huggingface dataset:
count=0
def merge(A, left, mid, right):
    global count
    n1=mid - left
    n2=right - mid
    L=[i for i in range(n1+1)]
    R=[i for i in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = 100000000
    R[n2] = 100000000
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
            count+=1
        else:
            A[k] = R[j]
            j = j + 1
            count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    for i,j in enumerate(A):
        if i == n-1:
            print(j)
        else:
            print(j,end=" ")
    print(count)


### FIXED CODE ###

count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)
N, A, B = map(int, input().split())

counter = [0 for _ in range(N)]
ans = 0
for i in range(N+1):
    st = str(i)
    for j in range(len(st)+1):
        counter[i] = counter[i] + st[j]
    if counter[i]>=A and counter[i]<=B :
        ans = ans + i

print(ans)

### FIXED CODE ###

N, A, B = map(int, input().split())
ans = 0

for i in range(1, N+1):
    num_sum = 0
    for j in str(i):
        num_sum += int(j)
    if A<= num_sum <= B:
        ans += i

print(ans)
import sys
from io import StringIO
import unittest
import numpy as np

def resolve():
    li = sys.stdin.readlines()
    N = int(li[0].strip())
    a = list(map(int, li[1].strip().split(' ')))
    A = np.array(a[0::2])
    A = (A % 2 == 1)
    print(A.sum())
resolve()



### FIXED CODE ###

import sys
from io import StringIO
import unittest
import numpy as np

def resolve():
    li = sys.stdin.readlines()
    N = int(li[0].strip())
    a = list(map(int, li[1].strip().split(' ')))
    A = np.array(a[0::2])
    A = (A % 2 == 1)
    print(A.sum())
resolve()
n = input()
A = []
for i in range(n):
   A.append(int(raw_input()))

q = input()
M = []
for i in range(n):
   M.append(int(raw_input()))

def solve(i, m)
   if m == 0
     return true
   if i >= n
     return false
   res = solve(i + 1, m) || solve(i + 1, m - A[i])
   return res

for i in range(len(M)):
   if solve(0,m):
      print "yes"
   else:
      print "no"

 

### FIXED CODE ###

n = input()
A = map(int, raw_input().split())
q = input()
M = map(int, raw_input().split())

def solve(i, m):
   if m == 0:
     return True
   if i >= n or m > sum(A):
     return False
   res = solve(i + 1, m) or solve(i + 1, m - A[i])
   return res

for m in M:
  if solve(0,m):
     print "yes"
  else:
     print "no"
n=int(input())
z=[list(map(int, input().split())) for i in range(n)]
z.sort(key=lambda x:x[2])
z.reverse()
print(z)

v=[]
count=0

#各頂点に対して、中心座標と仮定して検証
for i in range(101):
    for j in range(101):
            x=abs(j-z[0][0])
            y=abs(i-z[0][1])
            h=z[0][2]+abs(x)+abs(y)
                
            #候補があってるか確認
            for k in range(n):
                if z[k][2]==max(h-abs(z[k][0]-j)-abs(z[k][1]-i),0):
                    count+=1
                
            if count==n:
                print(r[0],r[1],h)
            exit()
        count=0

### FIXED CODE ###

n=int(input())
z=[list(map(int, input().split())) for i in range(n)]
z.sort(key=lambda x:x[2])
z.reverse()

v=[]
count=0

#各頂点に対して、中心座標と仮定して検証
for i in range(101):
    for j in range(101):
        x=abs(j-z[0][0])
        y=abs(i-z[0][1])
        h=z[0][2]+abs(x)+abs(y)
                
            #候補があってるか確認
        for k in range(n):
            if z[k][2]==max(h-abs(z[k][0]-j)-abs(z[k][1]-i),0):
                count+=1
                
        if count==n:
            print(j,i,h)
            exit()
        count=0
n = int(input())
def con_n(n):
    if n < 1000:
        return 'ABC'
    elif n => 1000:
        return 'ABD'
    
print(con_n(n))

### FIXED CODE ###

n = int(input())
def con_n(n):
    if n < 1000:
        return 'ABC'
    elif n >= 1000:
        return 'ABD'
    
print(con_n(n))
import numpy as np
import sys
input = sys.stdin.readline

def main():
    N,W = map(int,input().split())
    X = [list(map(int,input().split())) for _ in range(N)]
    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
    for i in range(N):
        for w in range(W+1):
            if X[i][0] <= w:
                dp[i+1][w] = max(dp[i][w-X[i][0]]+X[i][1],dp[i+1][w])
            else:
                dp[i+1][w] = dp[i][w]
    dp = np.array(dp)
    print(dp.max())

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N,W = map(int,input().split())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))

if __name__ == "__main__":
    main()
S = input().sprit()
n = len(S)

for i in range(n-2, 0, -2):
  S = S[:i]
  k = i // 2
  if S[k:] == S[:k]:
    print(i)
    exit()

### FIXED CODE ###

S = input().strip()
n = len(S)

for i in range(n-2, 0, -2):
  S = S[:i]
  k = i // 2
  if S[k:] == S[:k]:
    print(i)
    exit()
n,a,b = (int(i) for i in input().split())
x = [int(i) for i in input().split()]
answer = 0
for i in range(n-1):
	if (x[i+1]-x[i])*a < b: answer += (x[i+1]-x[i])*a
	else: answer += b
print(answer)

### FIXED CODE ###

n = int(input())
x,answer = [2],1
if n != 1:
	for i in range(2,n+1):
		if all(i%j != 0 for j in x):
			x.append(i)
	for i in x:
		num,num2 = 1,0
		while i**num<=n:
			a = i**num
			num2 += (n-n%a)//a
			num += 1
		answer = answer*(num2+1)%(10**9+7)
print(answer)
a, b, c = sorted([ int(v) for v in input().split() ])
n = int(input())
print(a+b+c*(2**k))

### FIXED CODE ###

a, b, c = sorted([ int(v) for v in input().split() ])
k = int(input())
print(a+b+c*(2**k))
import pandas as pd

n,m =map(int, input().split())  #複数数値入力
x=list(map(int, input().split()))  #リスト入力

x.sort()



if m == 1:
    print(0)
else:
    x_df = pd.Series(x)
    x_d_df = x_df.diff()
    x_d = x_d_df.values.tolist()
    x_d.pop(0)

    for i in range(n-1):
        x_d.remove(max(x_d))
#         print(x_d)
    
    sumd = sum(x_d)  
    print(sumd)

### FIXED CODE ###

import numpy as np
n,m =map(int, input().split())  #複数数値入力
x=list(map(int, input().split()))  #リスト入力

x.sort()
x_d = list()

if n > m:
    print(0)
else:
    if m == 1:
        print(0)
    else:
#         for i in range(m-1):
#             x_d.append(x[i+1] - x[i])   
        x_d = list(np.diff(x))

#         for i in range(n-1):
            
#             x_d.remove(max(x_d))
            
        x_d.sort(reverse=True)
#         sumd = sum(x_d)  
        sumd = sum(x_d[n-1:])
        print(sumd)
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
	int n; cin >> n;
    vector<ll> v(n);
    rep(i, n){
        cin >> v[i];
    }
    sort(All(v));
    if(v[0] == 0){
        cout << 0 << endl;
        return 0;
    }
    ll ans = v[n-1];
    for(int i = 0; i < n-1; i++){
        ans *= v[i];
        if(ans > (ll)1e18){
            cout << -1 << endl;
            return 0;
        }
    }
    if(ans < 0){
        cout << -1 << endl;
    }
    else cout << ans << endl;
    system("pause");
}


### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
ans = 1
if 0 in L:
  print(0)
  exit()
for i in range(N):
  ans *= L[i]
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
def count1(st):
    g = 0
    c = 0
    cont = False
    for p in st:
        if p == '1':
            if cont == False:
                c = 1
                cont = True
            else:
                c += 1
            g = max(g,c)
        else:
            cont = False
    return g
N,K = map(int,input().split())
s = input()
ls = len(s)
i = 0
il = 0
ir = 0
mg = 0
mgs = ''
if ls == 1:
    print(1)
else:
    for j in range(K):
        #print('j',j)
        while i < N:
            #print(s[i])
            if s[i] == '0':
                il = i
                while i < N:
                    if s[i] == '1':
                        ir = i - 1
                        break
                    i += 1
                #print('lr',il,ir)
                new_s = s[:il] + '1'*(ir-il+1) + s[ir+1:]
                #print(new_s)
                if mg < count1(new_s):
                    mg = count1(new_s)
                    mgs = new_s
                #print('mg',mg)
            else:
                i += 1
        s = new_s
        i = 0
    print(mg)
    #print(mg,mgs)

### FIXED CODE ###

N,K = map(int,input().split())
s = input()
#first
last = -1
ck = K
pre = ''
for i in range(N):
    c = s[i]
    if c == '0' and pre != '0':
        ck -= 1
        if ck < 0:
            last = i - 1
            break
    pre = c
else:
    last = N-1
#print('last:',last)

if last == N-1:print(len(s))
else:
    ## step by step
    cameLast = False
    ilr = 0
    g_max = 0
    while True:
        #print('calc g.:',last - ilr + 1)
        g_max = max(g_max,last - ilr + 1)
        if cameLast:break
        pre = ''
        for i in range(ilr,N):
            if s[i] == '1' and pre == '0':
                ilr = i
                break
            else:pre = s[i]
        else:#print('CANNOT REACH HERE!! - no next ilr')
            ilr = len(s) - 1
        prel = ''
        for j in range(last+1,N):
            if s[j] == '0' and prel == '1':
                last = j - 1
                break
            else:prel = s[j]
        else:#'reach last s[]'
            last = len(s) - 1
            cameLast = True
    print(g_max)
import math
N,Y= [int(i) for i in input().split()]
a=N+Y
if a%3 != 0:print(0)
else:
    b=a/3
    print(int((math.factorial(b)/math.factorial(abs(N-Y)))%(10**9+7)))

### FIXED CODE ###

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    #print(inv, q, gcd_val)
    return inv % m

def m(n,r):
    d=1
    e=1
    f=1
    for i in range(r):
        d=(n-i)
        e=(i+1)
        d%=(10**9+7)
        f = f*d*modinv(e,(10**9+7))%(10**9+7)
        
    return(f)

n=[int(i) for i in input().split()]
a=sum(n)
if a%3 != 0:print(0)

else:
    b=int(a/3)
    if b==1:
        print(1)
    else:
        c=n[0]-b
        d=n[1]-b
        if c<0 or d<0: print(0)

        else:
            if c==d:
                c=int(b/2)
            d=m(b,min(c,d))
            print(d%(10**9+7))
import bisect

N = int(input())
A = list(set(map(int, input().split())))
B = list(set(map(int, input().split())))
C = list(set(map(int, input().split())))
ans = 0
A.sort()
B.sort()
C.sort()
# print(A, B, C)
for i in range(N):
    b = B[i]
    a_i = bisect.bisect_left(A, b)
    c_i = bisect.bisect_right(C, b)
    cnt = (a_i) * (N - c_i)
    # print(b, a_i, c_i, cnt)
    ans += cnt

print(ans)

### FIXED CODE ###

import bisect

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
A.sort()
B.sort()
C.sort()
# print(A, B, C)
for b in B:
    a_i = bisect.bisect_left(A, b)
    c_i = bisect.bisect_right(C, b)
    cnt = (a_i) * (N - c_i)
    # print(b, a_i, c_i, cnt)
    ans += cnt

print(ans)
a=int(input())
import itertools
b=list(map(int,input().split()))
c=0
for d,e in combinations(b,2):
  c+=d*e
print(c)


### FIXED CODE ###

a=int(input())
import itertools 
b=list(map(int,input().split()))
c=0
for d,e in itertools.combinations(b,2):
  c+=d*e
print(c)
import math

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

floor = 0
ceil = max(a)


def cut(long, logs):
    cnt = 0
    for i in logs:
        cnt += math.ceil(i / long) - 1
    return cnt


while ceil - floor > 1:
    L = (ceil + floor)//2
    num = cut(L, a)
    if num <= k:
        ceil = L
    else:
        floor = L

print(ceil)

### FIXED CODE ###

n = int(input())

if n >= 30:
    print("Yes")
else:
    print("No")
import sys
from collections import deque
l,n=map(int,input().split())
p=n//2
q=(n-1)//2
r=(n+1)//2
tree1=[int(i) for i in sys.stdin]
reversed_tree1=[l-i for i in tree1]
tree=deque(tree1)
reversed_tree=deque(reversed_tree1)
if n%2 == 0:
  ans= 1
  ans2= 1
  p-=1
  ans3= ans-tree.popleft()*2-l+tree[p]*2
  ans= max(ans,ans3)
  ans4= ans2-reversed_tree.popleft()*2-l+(reversed_tree[p])*2
  ans2= max(ans2,ans4)
else:
  ans= 1
  ans3=ans
  ans2= 1
  ans4=ans2
while len(tree)>1:
  q-=1
  r-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[q]+tree[r]
  ans3=ans_stack
  p-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[p]*2
  ans3=ans_stack
p=n//2
q=(n-1)//2
r=(n+1)//2
while len(reversed_tree)>1:
  q-=1
  r-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[q]+reversed_tree[r]
  ans4=ans_stack
  p-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[p]*2
  ans4=ans_stack
print(max(ans,ans2))


### FIXED CODE ###

import sys
from collections import deque
l,n=map(int,input().split())
c=n
tree1=[int(i) for i in sys.stdin]
reversed_tree1=[l-i for i in reversed(tree1)]
tree=deque(tree1)
reversed_tree=deque(reversed_tree1)
if n%2 == 0:
  ans= sum(tree1)*2 + l*(n-1) +tree1[n//2] - sum(tree1[n//2:])*4
  ans2= sum(reversed_tree1)*2 + l*(n-1) +reversed_tree1[n//2] - sum(reversed_tree1[n//2:])*4
  n-=1
  c-=1
  ans3= ans-tree.popleft()*2-l+tree[n//2]*2
  ans= max(ans,ans3)
  ans4= ans2-reversed_tree.popleft()*2-l+(reversed_tree[n//2])*2
  ans2= max(ans2,ans4)
else:
  ans= sum(tree1)*2 + l*(n-1) - tree1[n//2] - sum(tree1[((n//2)+1):])*4
  ans3=ans
  ans2= sum(reversed_tree1)*2 + l*(n-1) - reversed_tree1[n//2] - sum(reversed_tree1[((n//2)+1):])*4
  ans4=ans2
for i in range(n//2):
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[(n-1)//2]+tree[(n+1)//2]
  ans= max(ans_stack,ans)
  ans3=ans_stack
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[n//2]*2
  ans=max(ans_stack,ans)
  ans3=ans_stack
n=c
for i in range(n//2):
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[(n-1)//2]+reversed_tree[(n+1)//2]
  ans2=max(ans_stack,ans2)
  ans4=ans_stack
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[n//2]*2
  ans2=max(ans2,ans_stack)
  ans4=ans_stack
print(max(ans,ans2))
n=input()
l=list(range(1,n))
m=0
while any(i%2==0 for i in l):
       l=[i/2 for i in l]
       m+=1
print(2**m)

### FIXED CODE ###

N=int(input())
c=0
n=range(1,N)
while any(i%2==0 for i in n):
          N=int(N/2)
          n=range(1,N+1)
          c+=1
print(2**c)
from collections import deque
MOD = 1000000007

N =  int(input())
childs = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    childs[a].append(b)
    childs[b].append(a)

dp = [0] * (N + 1) # represent the # if i is the root (1)
tree_size = [0]*(N + 1)
ans = [0] * (N + 1)

n_inv = [1, 1]
n_j_mod = [1, 1]

for i in range(2, N+1):
    n_inv.append((pow(i, MOD-2, MOD) * n_inv[-1]) % MOD)
    n_j_mod.append((n_j_mod[-1] * i) % MOD)


def dfs(i, father=-1):
    method_num = 1
    t_size = 1
    for child in childs[i]:
        if child != father:
            num, size = dfs(child, i)
            method_num = (method_num * num * n_inv[size]) % MOD
            t_size += size
    method_num = (method_num * n_j_mod[t_size - 1]) % MOD
    dp[i] = method_num
    tree_size[i] = t_size
    return method_num, t_size

def rdfs(i, f_num, father=-1):
    ans[i] = (dp[i] * f_num * n_j_mod[N-1] * n_inv[N - tree_size[i]] * n_inv[tree_size[i] - 1]) % MOD

    for child in childs[i]:
        if child != father:
            cf_num = (ans[i] * n_j_mod[tree_size[child]] * n_j_mod[N - tree_size[child] - 1] * n_inv[N - 1] * pow(dp[child], MOD-2, MOD)) % MOD
            rdfs(child, cf_num, i)
dfs(1)

rdfs(1, 1)
print('\n'.join(list(map(str, ans[1:]))))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from collections import deque
MOD = 1000000007

N =  int(input())
childs = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    childs[a].append(b)
    childs[b].append(a)

dp = [0] * (N + 1) # represent the # if i is the root (1)
tree_size = [0]*(N + 1)
ans = [0] * (N + 1)

n_inv = [1, 1]
n_j_mod = [1, 1]

for i in range(2, N+1):
    n_inv.append((pow(i, MOD-2, MOD) * n_inv[-1]) % MOD)
    n_j_mod.append((n_j_mod[-1] * i) % MOD)


def dfs(i, father=-1):
    method_num = 1
    t_size = 1
    for child in childs[i]:
        if child != father:
            num, size = dfs(child, i)
            method_num = (method_num * num * n_inv[size]) % MOD
            t_size += size
    method_num = (method_num * n_j_mod[t_size - 1]) % MOD
    dp[i] = method_num
    tree_size[i] = t_size
    return method_num, t_size

def rdfs(i, f_num, father=-1):
    ans[i] = (dp[i] * f_num * n_j_mod[N-1] * n_inv[N - tree_size[i]] * n_inv[tree_size[i] - 1]) % MOD

    for child in childs[i]:
        if child != father:
            cf_num = (ans[i] * n_j_mod[tree_size[child]] * n_j_mod[N - tree_size[child] - 1] * n_inv[N - 1] * pow(dp[child], MOD-2, MOD)) % MOD
            rdfs(child, cf_num, i)
dfs(1)

rdfs(1, 1)
print('\n'.join(list(map(str, ans[1:]))))
n,m = map(int,input().split())
edge = [[-1] for _ in range(n+1)]
for i in range(m):
    a,b = [int(i) for i in input().split()]
    edge[a].append(b)
    edge[b].append(a)
if(m&1==1):
    print(-1)
    exit()
print(edge)
for i in range(n+1):
    if len(edge[i])==2:
        l = edge[i][1]
        print(l,i)
        edge[l][0] -= 1
        edge[l].remove(i)
        edge[i].clear()
for i in range(n+1):
    if edge[i][0]%2==0:
        for e in edge[i][1:]:
            if edge[e][0]%2==1:
                print(i,e)
                edge[i][0] -= 1
                edge[i].remove(e)
                edge[e].remove(i)
for i in range(n+1):
    if len(edge[i])==2:
        l = edge[i][1]
        print(l,i)
        edge[l][0] -= 1
        edge[l].remove(i)
        edge[i].clear()
    for e in edge[i][1:]:
        if len(edge[e])==2:
            continue
        print(i,e)
        edge[i][0] -= 1
        edge[i].remove(e)
        edge[e].remove(i)
print(edge)


### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

n, m = map(int,input().split())
A = [[int(i) for i in input().split()] for i in range(m)]

if m&1:
    print(-1)
    exit()

E = [[] for i in range(n + 1)]
used_e = [False] * m
ans = []

for i, (a, b) in enumerate(A):
    E[a].append((b, i))
    E[b].append((a, i))

used = [False] * (n + 1)

def dfs(prev, v):
    if used[v]:
        return
    used[v] = True
    cnt = 0

    for to, i in E[v]:
        dfs(v, to)
        if not used_e[i]:
            cnt += 1

    for to, i in E[v]:
        if cnt % 2 == 1 and to == prev:
            continue
        if not used_e[i]:
            ans.append((v, to))
            used_e[i] = True

dfs(0, 1)

for a in ans:
    print(*a)
import bisect
#import numpy as np
N,K=[int(_) for _ in input().split()]
if N==4:
    raise
#A = np.array([int(_) for _ in input().split()],dtype=int)
#A.sort()
A=sorted([int(_) for _ in input().split()])

#target以下の積がK個以上ある最小のtarget


lb = -10**18-1
rb = 10 ** 18 + 1
# Min x for check(x) == True
while rb - lb > 1:
    target = (rb + lb) // 2
    if 1:
        cnt=0
        for i, a in enumerate(A):
            if a==0:
                d = i if target >= 0 else 0
                cnt+=d
                continue
            q,r=divmod(target,a)
            if a < 0:
                il = bisect.bisect_left(A,  q+(r>0))
                #il = bisect.bisect_left(A,  target / a)
                #il = np.searchsorted(A,target/a,side='left')
                #ilからiまで、ただしilがiを超えたら0
                d = max(i - il, 0)
            else:
                ir = bisect.bisect_right(A, q)
                #ir = bisect.bisect_right(A, target / a)
                #ir = np.searchsorted(A,target/a,side='right')
                #0からirまで、ただしirがiを超えたらi
                d = min(ir, i)
            #print(target,a,d)
            cnt+=d
    if cnt>=K:
        rb = target
    else:
        lb = target
print(rb)


### FIXED CODE ###

import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()


@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,target//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))
import math

n = int(input())
l = [0] * n
y = int(math.sqrt(n-3))
if n <= 5:
    for i in range(n):
        print(0)
for i in range(1,y):
    for j in range(1, y):
        for k in range(1, y):
            x = i ** 2 + j ** 2 + k ** 2 + i*j + i*k + j*k
            if x % 1 == 0 and x <= n:
                l[x-1] += 1
for i in l:
    print(i)

### FIXED CODE ###

import math
import sys

n = int(input())
l = [0] * n
if n < 6:
    for i in range(n):
        print(0)
    sys.exit()
y = int(math.sqrt(n-3))
if n <= 5:
    for i in range(n):
        print(0)
for i in range(1,y):
    for j in range(1, y):
        for k in range(1, y):
            x = i ** 2 + j ** 2 + k ** 2 + i*j + i*k + j*k
            if x % 1 == 0 and x <= n:
                l[x-1] += 1
for i in l:
    print(i)
N, X, T = map(int,inout().split())
takoyakitime=math.ceil(N/T/X)
print(takoyakitime)

### FIXED CODE ###

import math
N, X, T = map(int,input().split())
takoyakitime=math.ceil(N/X)
t_takoyakitime = takoyakitime*T
print(t_takoyakitime)
n = int(input())
k = int(input())
if n % k == 0:
    print(0)
else:
    print(1)

### FIXED CODE ###

n,k=map(int,input().split())   
if n%k == 0:
    print(0)
else:
    print(1)
N = int(input())
t0, a0 = 1, 1
for _ in range(N):
    t, a = map(int, input().split())
    n = max((t0- 1)// t+ 1, (a0-1)//a+1)
    t0, a0 = n*t, n*a

print(t0 + a0)

### FIXED CODE ###

li = set(map(int, input().split()))
print(len(li))
N = int(input())
A = [input().split() for i in range(N)]
dup = [j for j in set(A) if A.count(j) > 1]
if dup == True:
  print("NO")
else:
  print("YES")

### FIXED CODE ###

def has_duplicates(seq):
    return len(seq) != len(set(seq))
    
N = map(int,input())
A = list(map(int,input().split()))
print("NO" if has_duplicates(A) else "YES")