Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import sys


def binary_search(data, targets, n):
    cnt = 0
    for num in targets:
        small = 0
        big = n - 1
        while 1:
            index = (small + big) >> 1
            if num == data[index]:
                cnt += 1
                break
            if small == big:
                break
            if num < data[index]:
                big = index - 1
            elif num > data[index]:
                small = index + 1

    return cnt


if __name__ == "__main__":
    data = [val.split() for val in sys.stdin.read().splitlines()]
    print(binary_search(data[1], data[3], int(data[0][0])))

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys


def binary_search(data, targets, n):
    cnt = 0
    for num in targets:
        small = 0
        big = n - 1
        while small < big:
            index = (small + big) >> 1
            if small < big:
                if num < data[index]:
                    big = index - 1
                if num > data[index]:
                    small = index + 1
                if num == data[index]:
                    cnt += 1
                    break
        if small == big and num == data[small]:
            cnt += 1

    return cnt


if __name__ == "__main__":
    input_data = [val.split() for val in sys.stdin.read().splitlines()]
    n = int(input_data[0][0])
    data = [int(n) for n in input_data[1]]
    targets = [int(n) for n in input_data[3]]
    print(binary_search(data, targets, n))
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                ans += 1

print(ans)


### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if z >= 0 and z <= k:
            ans +=1
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
l = list(map(int, input().split()))
counter = 0
for v in itertools.combinations(l, 3):
     if 2 * max(v) < sum(v):
         counter += 1
print(counter)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
counter = 0
for i in range(n):
    for j in range(i + 1, n):
        counter += (bisect.bisect_left(l, l[i] + l[j]) - j - 1)
print(counter)
### BUGGY CODE ###

import sys
from pprint import pprint

S = sys.stdin.readline().strip()
S = S[::-1]

n = len(S)
r = [0] * 2019
acum = [0] * (len(S)+1)
r[0] += 1
for i, s_i in enumerate(S):
    acum[i+1] = int(s_i) * 10 ** (i) + acum[i]
    acum[i+1] %= 2019
    r[acum[i+1]] += 1
# print(acum)

ans = 0
for r_i in r:
    ans += r_i * (r_i - 1) // 2
print(ans)

### FIXED CODE ###

import sys
from pprint import pprint

S = sys.stdin.readline().strip()
S = S[::-1]

n = len(S)
r = [0] * 2019
acum = [0] * (len(S)+1)
r[0] += 1
for i, s_i in enumerate(S):
    acum[i+1] = int(s_i) * pow(10, i, 2019) + acum[i]
    acum[i+1] %= 2019
    r[acum[i+1]] += 1
# print(acum)

ans = 0
for r_i in r:
    ans += r_i * (r_i - 1) // 2
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
    ans*=i
print(-1 if ans>10**18 else ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
if 0 in a:
    ans=0
else:
    for i in a:
        ans*=i
        if ans>10**18:
            ans=-1
            break
print(ans)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
List=[]
for i in range(1,N):
  x=sum(a[0:i])
  y=sum(a[i:N])
  List.append(abs(x-y))
print(min(List))

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
List=[]
x1=a[0]
y1=sum(a[1:N])
List.append(abs(x1-y1))
for i in range(1,N-1):
  x1+=a[i]
  y1-=a[i]
  List.append(abs(x1-y1))
print(min(List))
### BUGGY CODE ###

N, K = [int(c) for c in input().split()]
S = [int(c) for c in input()]

clusters=[]
prev=-1
for s in S:
    if prev!=s:
        if prev!=-1:
            clusters.append((prev, seq))
        seq=0
    prev=s
    seq+=1
clusters.append((prev,seq))
clusters=[(1,0)] + clusters + [(1,0)]

ncls_0=0
for c in clusters:
    if c[0]==0:
        ncls_0 +=1

if ncls_0-K+1<=0:
    print(N)
    exit()

longest=0
for bgn_flip in range(ncls_0-K+1):
    clusters_copy=[]
    icls_0=-1
    ic_seq=[]
    for ic,c in enumerate(clusters):
        if c[0]==0:
            icls_0+=1
            if icls_0>=bgn_flip and icls_0 < bgn_flip+K:
                ic_seq.append(ic)

    seq=0
    for ic in range(ic_seq[0]-1,ic_seq[-1]+2):
        seq+=clusters[ic][1]
    if seq>longest:
        longest=seq

print(longest)


### FIXED CODE ###

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

n = 1
c = []
if S[0]=='0': c.append(0)
for i in range(1,N):
    if S[i]!=S[i-1]:
        c.append(n)
        n=1
    else:
        n+=1
c.append(n)
if S[-1]=='0': c.append(0)

t = sum(c[:2*K+1])
m = t
for i in range(2*K+1, len(c), 2):
    t += c[i] + c[i+1] - c[i-(2*K+1)] - c[i+1-(2*K+1)]
    m = max(m,t)

print(m)
### BUGGY CODE ###

n = int(input())
out=0

out = [i for i in range(n)]
out = sum(out)

print(out)


### FIXED CODE ###

n = int(input())
print(int((n-1)*n//2))
### BUGGY CODE ###

n, k = map(int, input().split())
kkn = [list(map(int, input().split())) for _ in range(k)]
MOD = 998244353

dp = [0]*(n+1)
dp[1] = 1
dpac = [0]*(n+1)
dpac[1] = 1
for i in range(2, n+1):
    for kl, kr in kkn:
        l = i-kr
        r = i-kl
        if r < 0: continue
        l = max(l, 0)
        dp[i] += dpac[r] - dpac[l-1]
    dpac[i] = dpac[i-1] + dp[i]
print(dp[n]%MOD)

### FIXED CODE ###

n, k = map(int, input().split())
kkn = [list(map(int, input().split())) for _ in range(k)]
MOD = 998244353

dp = [0]*(n+1)
dp[1] = 1
dpac = [0]*(n+1)
dpac[1] = 1
for i in range(2, n+1):
    for kl, kr in kkn:
        l = i-kr
        r = i-kl
        if r < 0: continue
        l = max(l, 0)
        dp[i] += dpac[r] - dpac[l-1]
        dp[i] %= MOD
    dpac[i] = dpac[i-1] + dp[i]
    dpac[i] %= MOD
print(dp[n])
### BUGGY CODE ###

A, B = map(int, input().split())
num = len(format(B, 'b'))
f = [format(i + A, 'b').zfill(num) for i in range(B - A + 1)]
x = [0] * num
for i in range(num):
    for j in range(B - A + 1):
        x[i] += int(f[j][i])
    x[i] = str(x[i] % 2)
print(int(str(''.join(x)), 2))

### FIXED CODE ###

A, B = map(int, input().split())
def f(x):
    if x % 4 == 0: return x
    elif x % 4 == 1: return 1
    elif x % 4 == 2: return x ^ 1
    elif x % 4 == 3: return 0
print(f(A - 1) ^ f(B))
### BUGGY CODE ###

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    n, a = reads()
    x = reads()
    s = sum(x)
    dp = [[[0]*(s+50) for j in range(n+1)] for i in range(n+1)]
    dp[0][0][0] = 1
    for i in range(n):
        for j in range(n):
            for k in range(s):
                dp[i][j+1][k] += dp[i][j][k]
                dp[i+1][j+1][k+x[j]] += dp[i][j][k]
    r = 0
    for j in range(1, n+1):
        r += dp[j][n][j*a]
    print(r)

main()


### FIXED CODE ###

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    n, a = reads()
    x = reads()
    s = sum(x)
    dp = [[[0]*3500 for j in range(n+1)] for i in range(n+1)]
    dp[0][0][0] = 1
    for i in range(n):
        for j in range(n):
            for k in range(s):
                dp[i][j+1][k] += dp[i][j][k]
                dp[i+1][j+1][k+x[j]] += dp[i][j][k]
    r = 0
    for j in range(1, n+1):
        r += dp[j][n][j*a]
    print(r)

main()
### BUGGY CODE ###

s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1

for i in range(1,len(s)):
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * (10**i) % 13 + r) % 13] += dp[i-1][r] % (10**9+7)
                
        else:
            dp[i][(int(s[-(i+1)]) * (10**i) % 13 + r) % 13] += dp[i-1][r] % (10**9+7)
            
print(dp[len(s)-1][5]%(10**9+7))


### FIXED CODE ###

s = input()
dp = [[0 for i in range(13)]]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    dp.append([0]*13)
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))
### BUGGY CODE ###

# R*r + G*g + B*b == N の数
R, G, B, N = map(int, input().split())
R, G, B = list(sorted([R, G, B], reverse=True))
ans = 0
for r in range(N + 1):
    for g in range(N + 1):
        if (N - (r * R + g * G)) % B != 0:
            continue
        b = (N - (r * R + g * G))/B
        if b < 0:
            break
        if r * R + g * G + b * B == N:
            ans += 1
        elif r * R + g * G + b * B > N:
            break
print(ans)


### FIXED CODE ###

# R*r + G*g + B*b == N の数
R, G, B, N = map(int, input().split())
R, G, B = list(sorted([R, G, B], reverse=True))
ans = 0
for r in range(N + 1):
    for g in range(N + 1):
        if (N - (r * R + g * G)) % B != 0:
            continue
        b = (N - (r * R + g * G))/B
        if b < 0:
            break
        if r * R + g * G + b * B == N:
            ans += 1
        elif r * R + g * G + b * B > N:
            break

print(ans)
### BUGGY CODE ###

def get_prime_factorized(N):
    result    = []
    base, exp = 2, 0
    while base ** 2 <= N:
        while N % base == 0:
            N    = N // base
            exp += 1
        if exp > 0:
            result.append([base, exp])
        base, exp = base + 1, 0
    if N > 1:
        result.append([N, 1])
    return result

def re_func_divisior(prime_factorized):
    base, exp = prime_factorized.pop()
    P = re_func_divisior(prime_factorized) if prime_factorized else [[]]
    Q = [[base ** k] for k in range(exp + 1)]
    return [p + q for p in P for q in Q]

def get_list_divisor(N, reverse=True):
    try:
        prime_factorized = get_prime_factorized(N)
        res    = re_func_divisior(prime_factorized)
        result = []
        for k in res:
            for i, x in enumerate(k):
                if i == 0:
                    r = x
                else:
                    r *= x
            result.append(r)
        result = sorted(result, reverse=reverse)
    except:
        result = [N]
    return result


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

X = get_list_divisor(sum(A))

is_break = False

for x in X:
    POS = sorted([a % x for a in A if a % x != 0])
    NEG = [x - pos for pos in POS]
    for sep in range(1, len(POS)):
        if sum(POS[:sep]) == sum(NEG[sep:]) and sum(POS[:sep]) <= K:
            is_break = True
            break
    if is_break:
        break

print(x)


### FIXED CODE ###

import numpy as np


def get_prime_factorized(N):
    result    = []
    base, exp = 2, 0
    while base ** 2 <= N:
        while N % base == 0:
            N    = N // base
            exp += 1
        if exp > 0:
            result.append([base, exp])
        base, exp = base + 1, 0
    if N > 1:
        result.append([N, 1])
    return result

def re_func_divisior(prime_factorized):
    base, exp = prime_factorized.pop()
    P = re_func_divisior(prime_factorized) if prime_factorized else [[]]
    Q = [[base ** k] for k in range(exp + 1)]
    return [p + q for p in P for q in Q]

def get_list_divisor(N, reverse=True):
    try:
        prime_factorized = get_prime_factorized(N)
        res    = re_func_divisior(prime_factorized)
        result = []
        for k in res:
            for i, x in enumerate(k):
                if i == 0:
                    r = x
                else:
                    r *= x
            result.append(r)
        result = sorted(result, reverse=reverse)
    except:
        result = [N]
    return result


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

X = get_list_divisor(sum(A))

is_break = False

for x in X:
    POS = sorted([a % x for a in A if a % x != 0])
    NEG = [x - pos for pos in POS]
    POS_cumsum = np.cumsum(POS)
    NEG_cumsum = np.cumsum(NEG[::-1])[::-1]
    for sep in range(1, len(POS)):
        if POS_cumsum[sep-1] == NEG_cumsum[sep] and POS_cumsum[sep-1] <= K:
            is_break = True
            break
    if is_break:
        break

print(x)
### BUGGY CODE ###

A, B, C, D = map(int, input().split())
cnt = 0
for i in range(A, B+1):
    if i%C != 0 and i%D != 0:
        cnt += 1

print(cnt)

### FIXED CODE ###

def gcd(a,b):
    r = a%b
    if r == 0:
        return b
    else:
        return gcd(b,r)

def lcm(a,b):
    return (a*b) // gcd(a,b)

A, B, C, D = map(int, input().split())

a1 = -(-A // C)
a2 = -(-A // D)
a3 = -(-A // lcm(C,D))

b1 = B // C
b2 = B // D
b3 = B // (lcm(C,D))

ans = (B-A+1) - ((b1-a1+1) + (b2-a2+1) - (b3-a3+1))
print(ans)
### BUGGY CODE ###

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

from itertools import accumulate
import bisect
cumsum_a = list(accumulate(a))
cumsum_b = list(accumulate(b))

ans = 0
for i in range(n+1):
    cnt_a = bisect.bisect(cumsum_a[:i], k)
    time = k - cumsum_a[cnt_a - 1]
    cnt_b = bisect.bisect(cumsum_b, time)
    
    ans = max(ans, cnt_a + cnt_b)

for i in range(m+1):
    cnt_b = bisect.bisect(cumsum_b[:i], k)
    time = k - cumsum_b[cnt_b - 1]
    cnt_a = bisect.bisect(cumsum_a, time)
    
    ans = max(ans, cnt_a + cnt_b)

print(ans)

### FIXED CODE ###

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

from itertools import accumulate
import bisect

A = [0] + list(accumulate(a))
B = list(accumulate(b))

ans = 0
for ac in range(n+1):
    if A[ac] > k:
        break
    bc = bisect.bisect_right(B, k-A[ac])
    ans = max(ans, ac+bc)

print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [i0]
    D = [1 << 100] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        x = hpop(h)
        d, i = x >> 10, x & 1023
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if nd > L: continue
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    x = nd * (1<<10) + j
                    hpush(h, x)
                    D[j] = nd
    return D
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if 0 <= D1[j] <= L:
            Y[i].append(j)

# print("X =", X)
# print("Y =", Y)
D2 = []
for i in range(N):
    D2.append(BFS(N, Y, i))

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    a = D2[s-1][t-1]-1
    ans.append(str(a if a >= 0 else -1))

print("\n".join(ans))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque
N, M, L = map(int, input().split())
D = [[1<<40] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j: continue
        if D[i][j] <= L:
            Y[i].append(j)
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D
D2 = []
for i in range(N):
    D2.append(BFS(N, Y, i))

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    a = D2[s-1][t-1]-1
    ans.append(str(a if a >= 0 else -1))
print("\n".join(ans))
### BUGGY CODE ###

l=input()
n=len(l)
mod=1000000007
dp=[0]*n
dp[0]=2
ans=(3**(n-1))%mod
for i in range(1,n):
  if l[i]=='0':
    dp[i]=dp[i-1]
  else:
    dp[i]=dp[i-1]*2
    ans+=(dp[i-1]*(3**(n-i-1)))%mod
print((ans+dp[n-1])%mod)


### FIXED CODE ###

l=input()
n=len(l)
mod=1000000007
dp=[0]*n
dp[0]=2
ans=[0]*n
ans[0]=1
for i in range(1,n):
  if l[i]=='0':
    dp[i]=(dp[i-1])%mod
    ans[i]=(ans[i-1]*3)%mod
  else:
    dp[i]=(dp[i-1]*2)%mod
    ans[i]=(ans[i-1]*3+dp[i-1])%mod
print((ans[n-1]+dp[n-1])%mod)
### BUGGY CODE ###

import sys

if __name__ == '__main__':
    n = int(sys.stdin.readline().rstrip())
    A = list(map(lambda x: int(x), sys.stdin.readline().split()))
    q = int(sys.stdin.readline().rstrip())
    B, C = [], []
    for i in range(q):
        b, c = list(map(lambda x: int(x), sys.stdin.readline().split()))
        B.append(b)
        C.append(c)

    for i in range(q):
        summ = 0
        for j in range(n):
            if A[j] == B[i]:
                A[j] = C[i]
            summ += A[j]
        print(summ)

### FIXED CODE ###

import sys
import numpy as np

if __name__ == '__main__':
    n = int(sys.stdin.readline().rstrip())
    A = list(map(lambda x: int(x), sys.stdin.readline().split()))
    q = int(sys.stdin.readline().rstrip())
    dic = {}
    for a in A:
        dic[a] = dic.get(a, 0) + 1

    # keys = list(dic.keys())
    # values = list(dic.values())
    # summ = np.array(keys).dot(np.array(values))
    summ = sum([k*v for k, v in dic.items()])
    for i in range(q):
        b, c = list(map(lambda x: int(x), sys.stdin.readline().split()))

        diff = c*dic.get(b,0) - b*dic.get(b,0)
        dic[c] = dic.get(c, 0) + dic.get(b, 0)
        dic[b] = 0
        summ += diff
        print(summ)
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
n = 10**6+1

dp = [0 for _ in range(max(A)+1)]

for i in A:
    dp[i] += 1
    if dp[i]==1:
        for j in range(i*2, max(A)+1, i):
            dp[j] = 2
    # print(dp)
print(dp.count(1))

### FIXED CODE ###

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

m_a = max(A)+1
dp = [0]*m_a

for i in A:
    dp[i] += 1
    if dp[i]==1:
        for j in range(i*2, m_a, i):
            dp[j] += 2
    # print(dp)
print(dp.count(1))
### BUGGY CODE ###

def main():
    s = input().rstrip()
    s = s[::-1]
    s += "0"
    n = len(s)
    a = [int(c) for c in s]
    dp = [[10**18]*2 for _ in range(2)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(2):
            x = a[i] + j
            if x < 10:
                dp[(i+1)%2][0] = min(dp[(i+1)%2][0], dp[i%2][j] + x + 0)
            if 0 < x:
                dp[(i+1)%2][1] = min(dp[(i+1)%2][1], dp[i%2][j] + 10 - x)
        for j in range(2):
            dp[i%2][j] = 10**18
    print(dp[n%2][0])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input().rstrip()
    s = "0" + s
    dp = [0, float("inf")]
    for c in s:
        x = int(c)
        dp = [min(dp[0] + x, dp[1] + (10-x)), min(dp[0] + x+1, dp[1] + (10-x) - 1)]
    print(dp[0])

if __name__ == "__main__":
    main()
### BUGGY CODE ###

from numba import jit


@jit
def solve(X, Y, Z):
    while X >= 0:
        if 2 * X + 4 * Z == Y:
            return True
        elif 2 * X + 4 * Z < Y:
            X -= 1
            Z += 1
    return False


def main():
    X, Y = map(int, input().split())
    Z = 0

    if solve(X, Y, Z):
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()


### FIXED CODE ###

from numba import jit


@jit
def solve(X, Y, Z):
    while X >= 0:
        if 2 * X + 4 * Z == Y:
            return True
        elif 2 * X + 4 * Z < Y:
            X -= 1
            Z += 1
        else:
            return False
    return False


def main():
    X, Y = map(int, input().split())
    Z = 0

    if solve(X, Y, Z):
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    dp = [[0] * n for _ in range(n)]
    for i, a in enumerate(aa):
        dp[i][i] = a
    # p2D(dp)
    for d in range(1, n):
        for l in range(n - 1):
            r = l + d
            if r >= n: break
            s0 = aa[l] - dp[l + 1][r]
            s1 = aa[r] - dp[l][r - 1]
            dp[l][r] = s0 if s0 > s1 else s1
    # p2D(dp)
    print(dp[0][-1])

main()


### FIXED CODE ###

def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  n, k = map(int, input().split())
  a, b, c = 0, 0, 0
  L, R = [], []
  for p in map(int, input().split()):
    if p < 0:
      a += 1
      L.append(p)
    elif p == 0:
      b += 1
    else:
      c += 1
      R.append(p)
  L.sort()
  R.sort()
  s = a*c
  t = b*(b-1)//2 + (a+c)*b
  if s < k <= s+t:
    ans = 0
  else:
    if k <= s:
      ok = -1
      ng = -(10**18+1)
      while ok - ng > 1:
        mid = (ok+ng)//2
        now = 0
        temp = 0
        for l in L:
          while now < c and l*R[now] > mid:
            now += 1
          temp += c - now
        if temp >= k:
          ok = mid
        else:
          ng = mid
    else:
      ok = 10**18
      ng = 0
      while ok - ng > 1:
        mid = (ok+ng)//2
        now = c - 1
        temp = s+t
        for i, r in enumerate(R):
          if now <= i:
            break
          while now > i and r*R[now] > mid:
            now -= 1
          temp += now - i
        now = 0
        for i in range(a-1, -1, -1):
          l = L[i]
          if now >= i:
            break
          while now < i and l*L[now] > mid:
            now += 1
          temp += i - now
        if temp >= k:
          ok = mid
        else:
          ng = mid
    ans = ok
  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a, b, c = 0, 0, 0
L, R = [], []
for p in map(int, input().split()):
  if p < 0:
    a += 1
    L.append(p)
  elif p == 0:
    b += 1
  else:
    c += 1
    R.append(p)
L.sort()
R.sort()
s = a*c
t = b*(b-1)//2 + (a+c)*b
if s < k <= s+t:
  ans = 0
else:
  if k <= s:
    ok = -1
    ng = -(10**18+1)
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = 0
      temp = 0
      for l in L:
        while now < c and l*R[now] > mid:
          now += 1
        temp += c - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  else:
    ok = 10**18
    ng = 0
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = c - 1
      temp = s+t
      for i, r in enumerate(R):
        if now <= i:
          break
        while now > i and r*R[now] > mid:
          now -= 1
        temp += now - i
      now = 0
      for i in range(a-1, -1, -1):
        l = L[i]
        if now >= i:
          break
        while now < i and l*L[now] > mid:
          now += 1
        temp += i - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  ans = ok
print(ans)