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

import sys
sys.setrecursionlimit(10**9)

MOD = 10**9 + 7

N, X = map(int, input().split())
Ss = list(map(int, input().split()))

Ss.sort(reverse=True)

def dfs(i, xNow):
    if (i, xNow) in memo:
        return memo[(i, xNow)]
    if i == N-1:
        ans = xNow % Ss[i]
    else:
        ans = dfs(i+1, xNow % Ss[i])
        ans += dfs(i+1, xNow) * (N-i-1)
    ans %= MOD
    memo[(i, xNow)] = ans
    return ans

memo = {}
dfs(0, X)

print(memo[(0, X)])


### FIXED CODE ###

MOD = 10**9 + 7

N, X = map(int, input().split())
Ss = list(map(int, input().split()))

Ss.sort(reverse=True)
minS = Ss[-1]

D = {X: 1}
for i, S in enumerate(Ss[:-1]):
    D2 = {}
    for x, num in D.items():
        D2[x] = (D2.get(x, 0) + num*(N-1-i)) % MOD
        D2[x%S] = (D2.get(x%S, 0) + num) % MOD
    D = D2

ans = 0
for x, num in D.items():
    ans += (x%minS) * num % MOD
    ans %= MOD

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

import numpy as np
import copy

n = int(input())
x = list(map(int, input().split()))
num = 0

y = copy.copy(x)
x.sort()

for i in range(n):
  num = x.index(y[i])
  if num >= n/2:
    print(x[int(n/2)-1])
  else:
    print(x[int(n/2)])

### FIXED CODE ###

import copy

n = int(input())
x = list(map(int, input().split()))
num = 0

y = copy.copy(x)
x.sort()
num1 = x[n//2-1]
num2 = x[n//2]

for i in y:
  if i <= num1:
    print(num2)
  else:
    print(num1)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

B = np.sort(A)[::-1]
B_index = np.argsort(A)[::-1]
dp = [[0]*(N+1) for _ in range(N+1)]

for x in range(0,N+1):
    for y in range(0,N+1-x):
        ind = B_index[x+y-1]
        if x==0 and y==0:
            dp[x][y] = 0
        elif x==0:
            dp[x][y] = dp[x][y-1] + B[x+y-1]*abs(ind-((N-1)-(y-1)))
        elif y==0:
            dp[x][y] = dp[x-1][y]+B[x+y-1]*abs(ind-(x-1))
        else:
            dp[x][y] = max(dp[x-1][y]+B[x+y-1]*abs(ind-(x-1)),dp[x][y-1] + B[x+y-1]*abs(ind-((N-1)-(y-1))))

print(np.max(dp))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = [[a,i] for a,i in zip(A,range(N))]
A = sorted(A,reverse=True)

dp = [[0]*(N+1) for _ in range(N+1)]
ans = 0

for n in range(0,N+1):
    for y in range(0,n+1):
        x = n-y
        a = A[n-1]
        ind = a[1]
        if x==0 and y==0:
            dp[x][y] = 0
        elif x==0:
            dp[x][y] = dp[x][y-1] + a[0]*abs(ind-((N-1)-(y-1)))
        elif y==0:
            dp[x][y] = dp[x-1][y]+a[0]*abs(ind-(x-1))
        else:
            dp[x][y] = max(dp[x-1][y]+a[0]*abs(ind-(x-1)),dp[x][y-1] + a[0]*abs(ind-((N-1)-(y-1))))
        ans = max(ans,dp[x][y])

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

def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    c=[0,2,5,5,4,5,6,3,7,6]
    cost=[0]*m
    for i,x in enumerate(a):
        cost[i]=c[x]
    dp=[0]*(n+10)
    ans=[]
    for i in range(n+1):
        for j in cost:
            dp[i+j]=max(dp[i]+1,dp[i+j])
    cnt=n
    while cnt>0:
        for i,j in enumerate(cost):
            if cnt>=j and dp[cnt-j]==dp[cnt]-1:
                ans.append(a[i])
                cnt-=j
                break
    print(''.join(map(str,ans)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

A.sort()
A.reverse()

match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-N-N] * (N + 1)
dp[0] = 0

for i in range(1, N + 1):
  for j in A:
    if i >= match[j]:
      dp[i] = max(dp[i], dp[i - match[j]] + 1)

max_list = []
while N:
  for j in A:
    if N >= match[j] and dp[N] == dp[N - match[j]] + 1:
      max_list.append(j)
      N -= match[j]
      break

for j in max_list:
  print(j, end="")
print("")
### BUGGY CODE ###

N, Q = map(int, input().split())
S= input()

for _ in range(Q):
  l, r= map(int, input().split())
  SP= S[l-1:r]
  print(SP.count("AC"))


### FIXED CODE ###

N, Q = map(int, input().split())
S= input()

count=[]
ans=0
for i in range (N):
  if i!=0 and S[i-1]=="A" and S[i]=="C":
    ans+=1
    count.append(ans)
  else:
    count.append(ans)
#print(count)

for _ in range(Q):
  l, r=map(int, input().split())
  print(count[r-1]-count[l-1])
### BUGGY CODE ###

h,w = map(int,input().split())

al = []

for _ in range(h):
    a = list(input())
    al.append(a)
c = 0
job = []
for i in range(h):
    for j in range(w):
        if al[i][j] == "#":
            job.append((i, j))
            c += 1
ans = 0
while True:
    if c == h*w:
        print(ans)
        import sys
        sys.exit()
    ans += 1
    job2 = []
    for y, x in job:
        vec = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for v in vec:
            xx = v[0] + x
            yy = v[1] + y
            if 0 <= xx < w and 0 <= yy < h:
                if al[yy][xx] == ".":
                    al[yy][xx] = "#"
                    job2.append((yy,xx))
                    c += 1
    job = job2
            



### FIXED CODE ###

h,w = map(int,input().split())

al = []

for _ in range(h):
    a = list(input())
    al.append(a)
c = 0
job = []
for i in range(h):
    for j in range(w):
        if al[i][j] == "#":
            job.append((i, j))
            c += 1
ans = 0
while True:
    if c == h*w:
        print(ans)
        import sys
        sys.exit()
    ans += 1
    job2 = []
    for y, x in job:
        vec = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for v in vec:
            xx = v[0] + x
            yy = v[1] + y
            if 0 <= xx < w and 0 <= yy < h:
                if al[yy][xx] == ".":
                    al[yy][xx] = "#"
                    job2.append((yy,xx))
                    c += 1
    job = job2
### BUGGY CODE ###

N = int(input())
r = [int(input()) for i in range(N)]

max_value = (-1)*(10 ** 9)
for j in range(1,len(r)):
    for i in range(0,j):
        max_value = max(max_value, r[j]-r[i])
print(max_value)

### FIXED CODE ###

# ??\?????????
N = int(input())
r = [int(input()) for i in range(N)]

# ?????§????¨????
max_profit = (-1) * (10 ** 9)
min_value = r[0]
for j in range(1, len(r)):
    max_profit = max(max_profit, r[j] - min_value)
    min_value = min(min_value, r[j])
print(max_profit)
### BUGGY CODE ###

import copy
import itertools
S = input()

K = 0
S__ = []

for i in reversed(range(len(S))):
    S_ = list(itertools.combinations(range(len(S) - 1), i))
    for j in S_:
        j = list(j)

        index = 0
        buff = ""
        S__ = []
        for k in range(len(S)):
            if index >= len(j):
                buff += S[k:]
                S__.append(buff)
                buff = ""
                break
            buff += S[k]

            if k == j[index]:
                S__.append(buff)
                buff = ""
                index += 1

        for k in range(len(S__) - 1):
            if S__[k] != S__[k+1]:
                if k == len(S__) - 2:
                    print(len(S__))
                    exit(0)
            else:
                break

### FIXED CODE ###

S = input()
ans = []

prev = ""
now = ""
for i in range(len(S)):
    now = now + S[i]
    if now != prev:
        ans.append(now)
        prev = now
        now = ""


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

from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(list)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].append(b)
    connect_dic[b].append(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = set(connect_dic[room_i])-next_connect_dic.keys()
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])

### FIXED CODE ###

from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(set)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = {connect_to for connect_to in connect_dic[room_i] if connect_to not in next_connect_dic.keys()}
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 0
for x in range(len(a)):
    c = 0
    for y in range (x):
       if a[y] < a[x]:
           c +=1
    if c == 0:
        b+=1
print(b)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 0
mini = 2*(10**5)+10
for x in range(len(a)):
    if a[x] < mini :
        mini=a[x]
        b+=1
print(b)
### BUGGY CODE ###

s = input()
n = len(s)

while True:
    if s.count('01') == 0 and s.count('10') == 0:
        break
    s = s.replace('01', '').replace('10', '')

_n = len(s)

print(n - _n)

### FIXED CODE ###

s = input()
set_ = set(['0', '1'])
arr = ['*']
for i in s:
    arr.append(i)
    if set(arr[-2:]) == set_:
        arr.pop()
        arr.pop()

ans = len(s) - len(arr) + 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = [0]*(n+1)
asum = 1

for i in range(2,n+1):
    a[i] += 1
    for k in range(i,n+1,i):
        a[k] += 1
    asum += i*a[i]
print(asum)

### FIXED CODE ###

n = int(input())
a = [0]*(n+1)
asum = 1

for i in range(2,n+1):
    a[i] += 1
    for k in range(i,n+1,i):
      a[k] += 1
    asum += i*a[i]
print(asum)
### BUGGY CODE ###

H,W,M = map(int,input().split())
Hinx = [0 for _ in range(H+1)]
Winx = [0 for _ in range(W+1)]
Hexist = [0 for _ in range(M)]
Wexist = [0 for _ in range(M)]
for i in range(M):
    h,w = map(int,input().split())
    Hinx[h] += 1
    Winx[w] += 1
    Hexist[i] = h
    Wexist[i] = w

HMinx = []
WMinx = []

Hmax = max(Hinx)
Wmax = max(Winx)
ans = Hmax+Wmax-1
for i in range(1,H+1):
    if Hinx[i] == Hmax:
        HMinx.append(i)
for i in range(1,W+1):
    if Winx[i] == Wmax:
        WMinx.append(i)

flag = False
for i in HMinx:
    for j in WMinx:
        flag2 = False
        for k in range(M):
            if Hexist[k] == i and Wexist[k] == j:
                flag2 = True
                break
        if flag2 == False:
            flag = True
            ans += 1
            break
    if flag == True:
        break
print(ans)


### FIXED CODE ###

H,W,M = map(int,input().split())
Hinx = [0 for _ in range(H+1)]
Winx = [0 for _ in range(W+1)]
isExist = []
for i in range(M):
    h,w = map(int,input().split())
    Hinx[h] += 1
    Winx[w] += 1
    isExist.append((h,w))

HMinx = []
WMinx = []
Hmax = max(Hinx)
Wmax = max(Winx)
ans = Hmax + Wmax

isExist = set(isExist)
for i in range(1,H+1):
    if Hinx[i] == Hmax:
        HMinx.append(i)
for i in range(1,W+1):
    if Winx[i] == Wmax:
        WMinx.append(i)

cross = 0
not_cross = 0

flag = True
for i in HMinx:
    for j in WMinx:
        if (i,j) not in isExist:
            flag = False
            break
    if flag == False:
        break
if flag == False:
    print(ans)
else:
    print(ans-1)
### BUGGY CODE ###

from bisect import bisect_left
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))

D.sort()
T.sort()

ans = 'YES'

for t in T:
  b = bisect_left(D,t)
  if D[b] != t:
    ans = 'NO'
    break
  else:
    D.pop(b)
    
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))

CD = Counter(D)
CT = Counter(T)
ans = CT - CD

if ans:
  print('NO')
else:
  print('YES')
### BUGGY CODE ###

def f(x):
    return x*(x-1)//2

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

d = collections.defaultdict(int)
for i in a:
    d[i]+=1

for i in a:
    ans=0
    for j in d:
        if j==i:
            ans+=f(d[j]-1)
        else:
            ans+=f(d[j])
    print(ans)

### FIXED CODE ###

def f(x):
    return x*(x-1)//2

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

d = collections.defaultdict(int)
for i in a:
    d[i]+=1
c = collections.defaultdict(int)
ans=0
for i in set(a):
    ans+=f(d[i])

for i in a:
    print(ans-(d[i]-1))
### BUGGY CODE ###

string=input()
length=len(string)
mod=[1]+[0]*2018
while length > 0:
  mod[int(string[length-1:])%2019]+=1
  length-=1
print(int(sum([(i*(i-1))/2 for i in mod])))


### FIXED CODE ###

string=input()
length=len(string)
mod=[1]+[0]*2018
s=0
for i in range(length):
  s=(s+int(string[-1-i])*pow(10,i,2019))%2019
  mod[s]+=1
print(sum([i*(i-1)//2 for i in mod]))
### BUGGY CODE ###

def main():
    N,M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    number = set(A)
    l = {n:0 for n in list(number)}
    for i in A:
        l[i] += 1
    for _ in range(M):
        B,C = map(int, input().split())
        f = False
        for i in number:
            if l[i] == 0:
                continue
            if B == 0:
                break
            if i < C:
                minus = min(l[i],B)
                if C not in l:
                    l[C] = 0
                l[C] += minus
                l[i] -= minus
                B -= minus
                f = True
        if f:
            number.add(C)
    ans = 0
    for k,v in l.items():
        ans += k*v
    print(ans)

main()

### FIXED CODE ###

n,m=map(int,input().split())
ans=list(map(int,input().split()))
arr=[list(map(int,input().split())) for _ in range(m)]
arr=sorted(arr,reverse=True,key=lambda x:x[1])
tmp=0
for cnt,val in arr:
  ans+=[val]*cnt
  tmp+=cnt
  if tmp>=n:
    break
ans=sorted(ans,reverse=True)
print(sum(ans[:n]))
### BUGGY CODE ###

from operator import itemgetter

D, G = map(int, input().split())
PC = [list(map(int, input().split())) for _ in range(D)]

def score(d, n, s, ans):
    if d == D:
        if s >= G:
            ans = min(ans, n)
        return ans
    p, c = PC[d]
    for k in range(p+1):
        if k == p:
            ans = score(d+1, n+k, 100*(d+1)*k + c + s, ans)
        else:
            ans = score(d+1, n+k, 100*(d+1)*k + s, ans)
    return ans

print(score(0, 0, 0, 1000))

### FIXED CODE ###

from operator import itemgetter

D, G = map(int, input().split())
PC = [list(map(int, input().split())) for _ in range(D)]

def com(d, s, ans):
    if d == D:
        ans.append(s)
        return ans
    a = s[:]
    a.append(1)
    ans = com(d+1, a, ans)
    b = s[:]
    b.append(0)
    ans = com(d+1, b, ans)
    return ans

L = com(0, [], [])
ans = 10000
for l in L:
    point = 0
    probs = 0
    uncom = []
    for i, com in enumerate(l):
        if com == 0:
            uncom.append(i)
        else:
            p, c = PC[i]
            point += (i+1)*100*p + c
            probs += p
    #print(probs, l)
    if point >= G:
        ans = min(ans, probs)
        continue
    uncom.sort(reverse=True)
    re = G - point
    for un in uncom:
        p, c = PC[un]
        #print(re, probs, p)
        if (un+1)*100*(p-1) >= re:
            rem = 1 if re % ((un+1)*100) > 0 else 0
            probs += re // ((un+1)*100) + rem
            re = 0
            break
        re -= (un+1)*100*(p-1)
        probs += p-1
    #print(probs)
    if re > 0:
        continue
    ans = min(ans, probs)
print(ans)
### BUGGY CODE ###

from collections import defaultdict


N = int(input())
A = list(map(int, input().split())) 
MOD = 10**9 + 7
def primes(num):
    if num == 1:
        d = defaultdict(int)
        d[1] = 1
        return d

    i = 2
    d = defaultdict(int)
    while i * i <= num:
        while num % i == 0:
            num //= i
            d[i] += 1
        i += 1
    if num > 1:
        d[num] += 1

    return d

d = primes(A[0])

for a in A[1:]:
    tmp_d = primes(a)
    dk = set(d.keys())
    tmp_dk = set(tmp_d.keys())
    dk = dk | tmp_dk
    for k in dk:
        d[k] = max(d[k], tmp_d[k])

lcm = 1

for k in d.keys():
    lcm *= pow(k, d[k]) % MOD


ans = 0
for i in range(N):
    ans += (lcm // A[i])
    ans %= MOD

print(ans)


### FIXED CODE ###

from fractions import gcd


def main():
        
    N = int(input())
    A = list(map(int, input().split())) 
    MOD = 10**9 + 7


    l = 1

    for a in A:
        l = l * a // gcd(l, a)


    ans = 0
    for a in A:
        ans += (l // a)
    ans %= MOD

    print(ans)


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

def dx(a,b):
    return abs(a-b)

def abs(x):
    if x>=0:
        return x
    else:
        return -x

if __name__ == '__main__':
    n = int(input())
    a = list(False for _ in range(n+2))
    a[0] = 0
    buf = list(map(int, input().split()))
    for i in range(n):
        a[i+1] = buf[i]
    a[n+1] = 0

    for i in range(1,n+1): ##訪れるのを取りやめる座標1->n
        pos = 0
        val = 0
        for j in range(n+2): ##訪れる座標0->(n+1)
            if i != j: ##訪れる座標なら
                val += dx(a[j], a[pos])
                pos = j
        print(val)

### FIXED CODE ###

n = int(input())
a = [0] + list(map(int, input().split())) + [0]
total = 0
for i in range(1, len(a)):
    total += abs(a[i] - a[i - 1])
for i in range(1, len(a) - 1):
    print(total - abs(a[i] - a[i - 1]) - abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[i - 1]))
### BUGGY CODE ###


# ans_list[i] : 13で割った余りがiの個数。これを入力の1桁目から更新していく。1桁目は以下


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_list = amari(n)
    l = len(amari_list)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            shift_list = [shift(j * amari_list[i % l] % n, ans_list)
                          for j in range(10)]

            ans_list = add(shift_list, mod)
        else:
            t = int(s) * amari_list[i % l] % n
            ans_list = shift(t, ans_list)

    print(ans_list[r] % mod)


def shift(r, num_list):
    l = len(num_list)
    return [num_list[(i + l - r) % l] for i in range(l)]


def add(num_list, mod):
    return [sum([num_list[i][j] for i in range(len(num_list))]) % mod for j in range(len(num_list[0]))]


def initial(s, n):
    if s == "?":
        return [1 if i < 10 else 0 for i in range(n)]
    else:
        return [1 if i == int(s) else 0 for i in range(n)]


def amari(n):
    ret = []
    for i in range(n+1):
        r = (10**i) % n
        if r in ret:
            return ret
        else:
            ret.append(r)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_l = amari_list(n)
    amari_m = amari_matrix(n, amari_l)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            ans_list = np.dot(ans_list, amari_m[i % len(amari_m)]) % mod
        else:
            t = int(s) * amari_l[i % len(amari_l)] % n
            ans_list = np.roll(ans_list, t)

    print(int(ans_list[r] % mod))


def initial(s, n):
    if s == "?":
        return np.array([1 if i < 10 else 0 for i in range(n)], dtype='int64')
    else:
        return np.array([1 if i == int(s) else 0 for i in range(n)], dtype='int64')


def shift(n, r):
    return np.array([[1 if (i - j + r) % n == 0 else 0 for j in range(n)] for i in range(n)])


def amari_list(n):
    ret = []
    for i in range(n + 1):
        r = 10**i % n
        if r in ret:
            return ret
        else:
            ret.append(r)


def amari_matrix(n, amari_list):
    ret = np.zeros((len(amari_list), n, n))
    for i, j in enumerate(amari_list):
        tmp = np.zeros((n, n))
        for k in range(10):
            tmp += shift(n, j * k % n)
        ret[i] = tmp
    return ret


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

import math
import itertools
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,k=map(int,input().split())
a=list(map(int, input().split()))
a=sorted(a)
mlist=[]
zlist=[]
plist=[]
for i in a:
  if i<0:
    mlist.append(i)
  elif i==0:
    zlist.append(i)
  else:
    plist.append(i)
mnum=len(mlist)
znum=len(zlist)
pnum=len(plist)
mans=mnum*pnum
zans=znum*(pnum+mnum)
if znum>=2:
  zans+=combinations_count(znum,2)
pans=0
if pnum>=2:
  pans+=combinations_count(pnum,2)
if mnum>=2:
  pans+=combinations_count(mnum,2)

if k<=mans:
  ans=[]
  for m in mlist:
    for p in plist:
      ans.append(m*p)
  ans=sorted(ans)
  print(ans[k-1])
elif k<=mans+zans:
  print(0)
else:
  k=k-(mans+zans)
  ans=[]
  for i in itertools.combinations(plist, 2):
    ans.append(i[0]*i[1])
  for i in itertools.combinations(mlist, 2):
    ans.append(i[0]*i[1])
  ans=sorted(ans)
  print(ans[k-1])


### FIXED CODE ###

import numpy as np
import sys
 
n,k=map(int,sys.stdin.readline().split())
a=np.array(list(map(int, input().split())))
 
a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]
 
def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2
 
 
left=-10**18
right=10**18
 
while left+1<right:
    x=(left+right)//2
    out=count(x)
    if out>=k:
        right=x
    if out<k:
        left=x
print(right)
### BUGGY CODE ###

import math

q = int(input())


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    for i in range(l, r + 1, 2):
        tmp += int(is_prime(i) and is_prime((i + 1) // 2))
    ans.append(tmp)

print(*ans, sep="\n")

### FIXED CODE ###

import numpy as np

q = int(input())

# 素数列挙
n = 10**5 + 1
primes = set(range(3, n+1, 2))
for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)

arr = np.array(list(primes))
arr = np.bincount(arr)

# 素数かつ2017に似た数を列挙
like_2017 = np.zeros(n, bool)
for i in np.where(arr == 1)[0]:
    if (i + 1) // 2 in primes:
        like_2017[i] = True

like_2017 = like_2017.cumsum()


def cnt_primes(l, r):
    return like_2017[r] - like_2017[l - 1]


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    tmp += cnt_primes(l, r)
    ans.append(tmp)

print(*ans, sep="\n")
### BUGGY CODE ###

import bisect
N=int(input())
A=list(map(int,input().split()))
B=[i+1 for i in range(N)]

C=[]
for i in range(N):
    C.append([A[i],B[i]])
C.sort()

L=[0,N+1]

ans=0

#print(C)
for i in range(N):
    ans+=C[i][0]*(L[bisect.bisect_right(L,C[i][1])]-C[i][1])*(C[i][1]-L[bisect.bisect_left(L,C[i][1])-1])
    L.insert(bisect.bisect_left(L,C[i][1]),C[i][1])
    #print(ans,L)
#print(L)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N=int(input())
a=list(map(int,input().split()))

b=[i for i in range(1,N+1)]

A=[]
for i in range(N):
    A.append([a[i],b[i]])
A.sort(reverse=True)
#print(A)
PL=[i for i in range(N+1)]+[N+1]
PR=[i for i in range(N+1)]+[N+1]

def findL(x):
    if x==PL[x]:
        return x
    else:
        return findL(PL[x])
        
def findR(x):
    if x==PR[x]:
        return x
    else:
        return findR(PR[x])
#print(PR)
ans=0
for i in range(N):
    ans+=A[i][0]*(A[i][1]-findL(A[i][1]-1))*(findR(A[i][1]+1)-A[i][1])
    #print(ans,A[i][1],(A[i][1]-findL(A[i][1])+1),findR(A[i][1])-A[i][1]+1)
    #print(PR)
    PL[A[i][1]]=findL(A[i][1]-1)
    PR[A[i][1]]=findR(A[i][1]+1)
print(ans)