Harryxun/stf_run huggingface dataset:
def p_grid(w, h):
	for i in range(h):
		for j in range(w):
			print(grid[j + w*i], end='')
		print()

def coloring():
    line = input()
    words = line.split()
    W = int(words[0])
    H = int(words[1])
    N = int(words[2])

    x = 0
    y = 0
    w = W
    h = H

    grid = []

    for i in range(h):
        for j in range(w):
            grid.append(0)

    for i in range(N):
      s = input()
      ws = s.split()
      x = int(ws[0])
      y = int(ws[1])
      a = int(ws[2])
      if a == 1 or a==3:
        #rect = x * y
        for i in range(y):
            for j in range(x):
                grid[j + w * i] = 1

        for i in range(h):
		    for j in range(w):
			    print(grid[j + w*i], end='')
		    print()

      if a == 2:
        #rect = (w - x) * y
        for i in range(y):
            for j in range(x,w):
                grid[j + w*i] = 1

        for i in range(h):
		    for j in range(w):
			    print(grid[j + w*i], end='')
		    print()

      if a == 4:
        #rect = x * (h - y)
        for i in range(y,h):
            for j in range(x):
                grid[j + w*i] = 1

        for i in range(h):
		    for j in range(w):
			    print(grid[j + w*i], end='')
		    print()
        
    print(grid.count(0))




coloring()

### FIXED CODE ###

def coloring():
    line = input()
    words = line.split()
    W = int(words[0])
    H = int(words[1])
    N = int(words[2])

    x = 0
    y = 0
    w = W
    h = H

    grid = []

    for i in range(h):
        for j in range(w):
            grid.append(0)

    for i in range(N):
        s = input()
        ws = s.split()
        x = int(ws[0])
        y = int(ws[1])
        a = int(ws[2])
        if a == 1:
            #rect = x * whole
            for i in range(h):
                for j in range(x):
                    grid[j + w * i] = 1

        if a == 2:
            #rect = (w - x) * whole
            for i in range(h):
                for j in range(x,w):
                    grid[j + w*i] = 1

        if a==3:
            #rect = whole * y
            for i in range(y):
                for j in range(w):
                    grid[j + w * i] = 1
        
        if a == 4:
            #rect = whole * (h - y)
            for i in range(y,h):
                for j in range(w):
                    grid[j + w*i] = 1

        
    print(grid.count(0))


coloring()
n = int(input())
a = list(map(int, input().split()))
a_sort = sorted(a)

for i, name in enumerate(a):
  a_sort[name-1] = i + 1
print(' '.join(a_sort))


### FIXED CODE ###

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

for i, name in enumerate(a):
  a_sort[name-1] = str(i + 1)
print(' '.join(a_sort))
n,m=map(int,input().split())
ans=int
ans=n/m
print(int(ans)+1)


### FIXED CODE ###

n,m=map(int,input().split())
ans=float
ans=n/m
if ans == 0:
    print(1)
elif ans == int(ans):
    print(int(ans))
else:
    print(int(ans)+1)
import sys

N, Y = map(int, input().split())
for x in range(N+1):
	for y in range(N+1-x):
		for z in range(N+1-x-y):
   			if Y == 10000*x+5000*y+1000*z :
    			print(x,y,z)
    			sys.exit()
print("-1 -1 -1")

### FIXED CODE ###

s = input()
print("2018/01/"+s[8:])
import fractions
#import math
n,x = map(int,input().split())
x = list(map(int,input().split()))
x.sort()

if n == 1:
    print(x[0]-1)
    exit()
a = x[1] - x[0]
b = x[2] - x[1]

print(fractions.gcd(a,b))
#print(math.gcd(a,b))


### FIXED CODE ###

import fractions

n, k = map(int, input().split())
x = list(map(int, input().split()))
x = [abs(x[i] - k) for i in range(n)]
ans = x[0]
for i in range(1, n):
    ans = fractions.gcd(ans, x[i])
print(ans)
C = [0]*3
C1 = [[0]*2]*3
C2 = [[0]*3]*2
for i in range(3):
  C[i] = list(map(int, input().split()))
for i in range(3):
  for j in range(2):
    C1[i][j] = C[i][j] - C[i][j+1]
for i in range(2):
  for j in range(3):
    C2[i][j] = C[i][j] - C[i+1][j]
if(C1[0][0] == C1[1][0] == C1[2][0]):
  if(C1[0][1] == C1[1][1] == C1[2][1]):
    if(C2[0][0] == C2[0][1] == C2[0][2]):
      if(C2[1][0] == C2[1][1] == C2[1][2]):
  print("No")
  exit()
print("No")

### FIXED CODE ###

C = [0]*3
C1 = [[0]*2]*3
C2 = [[0]*3]*2
flg = False
for i in range(3):
  C[i] = list(map(int, input().split()))
for i in range(2):
  for j in range(2):
    if(C[i][j] -C[i][j+1] != C[i+1][j] -C[i+1][j+1]):
      flg = True
for i in range(2):
  for j in range(2):
    if(C[i][j] -C[i+1][j] != C[i][j+1] -C[i+1][j+1]):
      flg = True
print("No" if flg else "Yes")
import sys
from collections import defaultdict, deque
import math

# import copy
# from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7

def divide(k):
    return pow(k, MOD-2, MOD)


def make_nck(n):
    ret = [1]
    for i in range(1, n+1):
        ret.append((ret[-1] * (n + 1 - i) * divide(i)) % MOD)

    # print(ret)
    return ret

def make_nigojyo(n):
    ret = [1]

    for i in range(1, n+1):
        ret.append((ret[-1] * 25) % MOD)

    # print(ret)
    return ret


def solve():
    n = getN()
    a = getList()
    ans = 0
    for i, j in zip(a, a[1:]):
        ans += min(i, j)
    ans += a[0] + a[-1]

    print(ans)



def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()import sys
from collections import defaultdict, deque
import math

# import copy
# from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7

def divide(k):
    return pow(k, MOD-2, MOD)


def make_nck(n):
    ret = [1]
    for i in range(1, n+1):
        ret.append((ret[-1] * (n + 1 - i) * divide(i)) % MOD)

    # print(ret)
    return ret

def make_nigojyo(n):
    ret = [1]

    for i in range(1, n+1):
        ret.append((ret[-1] * 25) % MOD)

    # print(ret)
    return ret


def solve():
    n = getN()
    a = getList()
    ans = 0
    for i, j in zip(a, a[1:]):
        ans += min(i, j)
    ans += a[0] + a[-1]

    print(ans)



def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()
INF = 100000000000
nums = [INF] + getList() + [INF]
ans = 0
for i, j in zip(nums, nums[1:]):
    ans += min(i, j)

print(ans)
N,K = map(int, input().split())
list = []
for i in range(N):
    list.append(int(input()))

print(-(-(N-1)//(K-1)))

### FIXED CODE ###

N,K = map(int, input().split())
print(-(-(N-1)//(K-1)))
import sys
n,m,X,Y=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
for z in range(101):
  if X<z<Y and x[i]<z for i in range(n) and y[j]>=z for j in range(m):
    print('No War')
    sys.exit()
for z in range(1,101):
  if X<z*(-1)<Y and x[i]<z*(-1) for i in range(n) and y[j]>=z*(-1) for j in range(m):
    print('No War')
    sys.exit()
print('War')


### FIXED CODE ###

import sys
n,m,X,Y=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
for z in range(101):
  if X<z<=Y and all(x[i]<z for i in range(n)) and all(y[j]>=z for j in range(m)):
    print('No War')
    sys.exit()
for z in range(1,101):
  if X<z*(-1)<=Y and all(x[i]<z*(-1) for i in range(n)) and all(y[j]>=z*(-1) for j in range(m)):
    print('No War')
    sys.exit()
print('War')
N, M = list(map(int, input().split()))
a = []
for i in range(0, M):
    a.append(int(input()))
a.sort()
T = 10 ** 9 + 7

r = [0 for _ in range(N + 1)]
r[0] = 1
r[1] = 1


def fib(n):
    if r[n] > 0:
        return r[n]
    else:
        return fib(n - 1) + fib(n - 2)


for i in range(0, M - 1):
    if a[i] + 1 == a[i + 1]:
        print(0)
        break
else:
    now = 0
    c = 1
    for i in range(0, M):
        c *= fib(a[i] - now - 1) % T
        c %= T
        now = a[i] + 1
    c *= fib(N - now)
    print(c % T)

### FIXED CODE ###

N, M = list(map(int, input().split()))
As = set()
for i in range(0, M):
    As.add(int(input()))
C = 10 ** 9 + 7

dp = [0 for _ in range(N + 1)]
dp[0] = 1
dp[1] = 0 if 1 in As else 1

for i in range(2, N + 1):
    if i in As:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % C

print(dp[N])
n,k=map(int,input().split())
a=list(map(int,input().split()))
dict={}
for i in range(n):
    dict[i]=a[i]-1 #i番目の町からどこにつくか
tmp=0#現在知
num2city={}
city2num={}
city2num[0]=0#どのまちが何回目か
num2city[0]=0#j回目にどこにいるか
for j in range(k):
    tmp=dict[tmp]#現在地更新
    if tmp not in num2city.values():#現在地がまだきたことない
        num2city[j]=tmp
        city2num[tmp]=j
    else:
        mae=city2num[tmp]
        term=j-mae 
        res=k-j-1
        r=res%term
        #print(mae,term,res,r)
        temp=num2city[mae+r]
        break
  #  print(tmp+1)
    

print(tmp+1)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dict={}
for i in range(n):
    dict[i]=a[i]-1 #i番目の町からどこにつくか
tmp=0#現在知
num2city={}
city2num={}
city2num[0]=0#どのまちが何回目か
num2city[0]=0#j回目にどこにいるか
alre=[-1]*n
alre[0]=1
for j in range(1,k+1):
    if tmp==dict[tmp]:
        break
    tmp=dict[tmp]#現在地更新
    if alre[tmp]==-1:#tmp not in num2city.values():#現在地がまだきたことない
        alre[tmp]=1
        num2city[j]=tmp
        city2num[tmp]=j
    else:
        mae=city2num[tmp]
        term=j-mae 
        res=k-j
        r=res%term
  #      print(mae,term,res,r,mae+r,num2city[mae+r])
        tmp=num2city[mae+r]
 #       print(tmp)
        break
   # print(tmp+1)
    
#print(num2city)
#print(city2num)
print(tmp+1)
n = int(input())
a = list(map(int, input().split()))

if len(set(a)) == 1:
    if set(a)[0] != 1:
        print(-1)
        exit()
    else:
        print(0)
        exit()

x = 1
count = 0

for i in a:
    if i == x:
        x+=1
    else:
        count+=1

print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if n == 1:
	if a[0] == 1:
		print (0)
		exit()
	else:
		print (-1)
		exit()
if len(set(a)) == 1 and a[0] != 1:
	print (-1)
	exit()
 
x = 1
cnt = 0
for i in a:
	if i == x:
		x += 1
	else:
		cnt += 1
if cnt == n:
	print (-1)
else:
	print(cnt)
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

#読書時間を机A,Bそれぞれについて上から順に加算
A_min = [0]
for i in range(N):
  A_min.append(A_min[i]+A[i])
B_min = [0]
for i in range(M):
  B_min.append(B_min[i]+B[i])

#A_min,B_minを順に加算して、Kを超えていなければ冊数を更新
ans = 0
B_len = len(B_min)
for i in range(len(A_min)):
  if A_min[i] > K:
    break
  while true:
    if B_min[B_len] > K - A_min[i]:
      break
    ans = max(ans,i+B_len)

print(ans)

### FIXED CODE ###

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

#読書時間を机A,Bそれぞれについて上から順に加算
A_min = [0]
for i in range(N):
  A_min.append(A_min[i]+A[i])
B_min = [0]
for i in range(M):
  B_min.append(B_min[i]+B[i])

#A_min,B_minを順に加算して、Kを超えていなければ冊数を更新
ans = 0
B_len = M
for i in range(len(A_min)):
  if A_min[i] > K:
    break
  while B_min[B_len] > K - A_min[i]:
    B_len -= 1
  ans = max(ans,i+B_len)
print(ans)
from sympy import sieve

def yakusuu(a):
    t = []
    for i in range(1,a+1):
        if a%i==0:
            t.append(i)
    return t

def kouyakusuu(a,b):
    t = []
    u = 0
    d = 0
    if a>b:
        u = a
        d = b
    else:
        u = b
        d = a
    for i in range(1,d+1):
        if u%i==0 and d%i==0:
            t.append(i)
    return t

a,b = map(int,input().split())

#t = list(map(yakusuu,kouyakusuu(a,b)))
t = kouyakusuu(a,b)
sn = 0
for i in t:
    if i in sieve:
        sn += 1

sn += 1

ans = sn*(sn-1)/2
print(ans)

### FIXED CODE ###

import math

A, B = [int(item) for item in input().split()]

def gdc(A, B):
    if B == 0:
        return A
    else:
        return gdc(B, A % B)

def chk_pn(num):
    flag = True
    if num  <= 3:
        pass
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                flag = False
                break
    return flag

def mk_factor(num):
    max_divisor = int(math.sqrt(num))+1
    divisor = 2
    factor_list = [1]

    while divisor <= max_divisor:
        if num % divisor == 0:
            factor_list.append(divisor)
            num /= divisor
        else:
            divisor += 1
    if num != 1.0:
        factor_list.append(num)
    return factor_list

GDC = gdc(A, B)
#pn_factor = [i for i in mk_factor(GDC) if chk_pn(i) is True]

print(len(set(mk_factor(GDC))))
import typing as tp
import fileinput
    
def frog(stones):
    stone_cost = [0]
    for i in range(1, len(stones)):
        single_step_cost = abs(stones[i] - stones[i - 1])
        if i == 1:
            stone_cost.append(single_step_cost)
        else:
            double_step_cost = abs(stones[i] - stones[i - 2])
            stone_cost.append(min(single_step_cost + stone_cost[-1], double_step_cost + stone_cost[-2]))
    
    return stone_cost[-1]
    
    
inp = fileinput.input()
inp.readline()
stones = [int(v) for v in inp.readline().split(" ")]
print(frog(stones))

### FIXED CODE ###

import fileinput
    
def frog(stones):
    stone_cost = [0]
    for i in range(1, len(stones)):
        single_step_cost = abs(stones[i] - stones[i - 1])
        if i == 1:
            stone_cost.append(single_step_cost)
        else:
            double_step_cost = abs(stones[i] - stones[i - 2])
            stone_cost.append(min(single_step_cost + stone_cost[-1], double_step_cost + stone_cost[-2]))
    
    return stone_cost[-1]
    
    
inp = fileinput.input()
inp.readline()
stones = [int(v) for v in inp.readline().split(" ")]
print(frog(stones))
from itertools import product

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = [ai + bi for (ai, bi) in product(a, b)]
ab.sort(reverse=True)
abc = [abi + ci for (abi, ci) in product(ab[: min(k, x * y * z)], c)]
abc.sort(reverse=True)

for abci in abc[: min(k, x * y * z)]:
    print(abci)


### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

d = e - a
k = int(input())

ans = "Yay!" if k >= d else ":("
print(ans)
import collections
import math
 
def combinations_count(n, r):
    return 0 if n < r else math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

combi = collections.Counter(A)
for k, v in combi.items():
  if v <= 1:
    combi.pop(k)
#print(combi)

for i in range(N):
  ans = 0
  
  # i番目の要素をcombiからdecrement
  combi[A[i]] -= 1
  
  #print(combi)
  
  for v in combi.values():
    #print(v)
    ans += combinations_count(v, 2)
  
  print(ans)

  # i番目の要素をcombiからincrement
  combi[A[i]] += 1

### FIXED CODE ###

import collections
import math
 
def combinations_count(n, r):
  if n == r:
    return 1
  elif n < r:
    return 0
  else:
    return n * (n-1) // 2 
    #math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

combi = collections.Counter(A)
combi_count = {}
calc_dict = {}
total = 0
for k, v in combi.items():
  if v in calc_dict:
    combi_count[k] = calc_dict[v]
  else:
    combi_count[k] = combinations_count(v, 2)
    calc_dict[v] = combi_count[k]
  total += combi_count[k]

for i in range(N):
  ans = total - combi_count[A[i]] + combinations_count(combi[A[i]]-1, 2)
  print(ans)
n, k = map(int,input().split())
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**9)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in range(k):
    ans = 0
    ans += cmb(n-k+1,i+1)*cmb(k-1,i)
    ans %= MOD
    print(ans)

### FIXED CODE ###

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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


for i in range(k):
    print(cmb(n-k+1,i+1,mod)*cmb(k-1,i,mod)%mod)
h,w=map(int,input().split())
ans=h*w
if h>2:
    t=[h//3*w,(h-(h//3))//2*w,(h-(h//3)+1)//2*w]
    t.sort()
ans=min(ans,t[2]-t[0])
if w>2:
    t=[w//3*h,(w-(w//3))//2*h,(w-(w//3)+1)//2*h]
    t.sort()
ans=min(ans,t[2]-t[0])
a,b=h,w
for i in range(max(1,a//3-1),min(a//2+1,a-1)):
    t=[i*b,(a-i)*(b//2),(a-i)*((b+1)//2)]
    t.sort()
    ans=min(ans,t[2]-t[0])
a,b=w,h
for i in range(max(1,a//3-1),min(a//2+1,a-1)):
    t=[i*b,(a-i)*(b//2),(a-i)*((b+1)//2)]
    t.sort()
    ans=min(ans,t[2]-t[0])
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

h,w=map(int,input().split())
ans=h*w
if h*w%3==0:
    print(0)
else:
    for x,y in ((h,w),(w,h)):
        x1=x//3
        x2=(x+2)//3
        y1=y//2
        y2=(y+1)//2
        ans=min(ans,abs(y*x2-y*x1))
        t=(y*x1,y2*(x-x1),(y-y2)*(x-x1))
        ans=min(ans,max(t)-min(t))
        t=(y*x2,y2*(x-x2),(y-y2)*(x-x2))
        ans=min(ans,max(t)-min(t))
    print(ans)
# your code goes here
def gcd(a,b):
    if b>a:
        t=b
        b=a
        a=t
    while b>0:
        r=a%b
        a=b
        b=r
    return a
N=int(input())
T=[int(input()) for i in range(N)]
g=gcd(T[0],T[1])
for i in range(1,N-1):
    g=gcd(T[i],g)
M=g
for i in range(N):
    M*=T[i]//g
print(M)

### FIXED CODE ###

# your code goes here
def gcd(a,b):
    if b>a:
        t=b
        b=a
        a=t
    a1=a
    b1=b
    while b1>0:
        r=a1%b1
        a1=b1
        b1=r
    a//=a1
    a*=b
    return a
N=int(input())
T=[int(input()) for i in range(N)]
if N==1:
    print (T[0])
else:
    m=gcd(T[0],T[1])
    i=2
    while i <N:
        m=gcd(m,T[i])
        i+=1
    print(m)
N, K = map(int, input().split())
V = list(map(int, input().split()))

if K <= 2:
    print(max(V[0], V[1], 0))
    quit()


ans = 0
for a in range(min(N, K)+1):
    for b in range(min(N-a, K-a)+1):
        V_ = sorted(V[:a] + V[-b:]) if b >= 1 else sorted(V[:a])
        tmp = K - (a+b)
        curMinus = 0
        for v in V_:
            if v < 0 and tmp > 0:
                tmp -= 1
                curMinus += -v
        ans = max(ans, sum(V_)+curMinus)

print(ans)

### FIXED CODE ###

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

if K <= 2:
    print(max(V[0], V[-1], 0))
    quit()


ans = 0
for a in range(min(N, K)+1):
    for b in range(min(N-a, K-a)+1):
        V_ = sorted(V[:a] + V[-b:]) if b >= 1 else sorted(V[:a])
        tmp = K - (a+b)
        curMinus = 0
        for v in V_:
            if v < 0 and tmp > 0:
                tmp -= 1
                curMinus += -v
        ans = max(ans, sum(V_)+curMinus)

print(ans)
import sys

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

if k==0:
    print(max(a))
    sys.exit()

def rf(mm):
    icnt=0
    for i in range(n):
        icnt+=(a[i]-1)//mm+1
    return icnt

asum=sum(a)
m=asum//(n+k)
um=asum
lm=1
for ii in range(60):
#while True:
    print(m,rf(m))
    if rf(m)>(n+k):
        lm=m
        m=(um+m)//2
    elif rf(m)<(n+k):
        um=m
        m=(lm+m)//2
    else:
        print(m)
        break

for mi in range(m,0,-1):
    if rf(mi)!=(n+k):
        break
print(mi+1)


### FIXED CODE ###

import sys

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

if k==0:
    print(max(a))
    sys.exit()

def rf(mm):
    if mm==0:
        mm=1
    icnt=0
    for i in range(n):
        icnt+=(a[i]-1)//mm+1
    return icnt

asum=sum(a)
m=asum//(n+k)
um=asum
lm=1
for ii in range(60):
    if m==1:
        break
    if rf(m)<=(n+k) and rf(m-1)>(n+k):
        break
    if um-lm<5:
        break
    if rf(m)>(n+k):
        lm=m
        m=(um+lm)//2-1
    elif rf(m)<(n+k):
        um=m
        m=(um+lm)//2-1
    else:
        um=m-1
        m=(um+lm)//2-1
#    if rf(m)==(n+k) and um-lm<5:

if um<1:
    print(1)
    sys.exit()
    
for mi in range(um,max(0,lm-1),-1):
    if rf(mi)<=(n+k) and rf(mi-1)>(n+k):
        break

print(mi)
S = str(input())

if S[0] == S[1] or S[1]==S[2] or S[2]==S[3] or S[3]==S[4]:
  print('Bad')
else:
  print('Good')

### FIXED CODE ###

S = str(input())

if S[0] == S[1] or S[1]==S[2] or S[2]==S[3]:
  print('Bad')
else:
  print('Good')
n,m=map(int, input().split())
h=list(map(int, input().split()))
near=[[] for i in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    near[a-1].append(h[b-1])
    near[b-1].append(h[a-1])
cnt=0
for i in range(n):
    if max(near[i])<=h[i]:
        cnt+=1
print(cnt)

### FIXED CODE ###

n,m=map(int, input().split())
h=list(map(int, input().split()))
near=[[0] for i in h]
for i in range(m):
    a,b=map(int, input().split())
    near[a-1].append(h[b-1])
    near[b-1].append(h[a-1])
cnt=0
for i in range(n):
    if max(near[i])<h[i]:
        cnt+=1
print(cnt)
N=int(input())
#N以下の正の整数の文字列を生成



list_a=np.arange(1, N+1)
list_b =[]


#print(list_a)
#print(len(str(list_a)))

for i in list_a:
    if  len(str(i))%2 !=0:
        #print(i)
        list_b.append(i)

print(len(list_b))



### FIXED CODE ###

import numpy as np
N=int(input())
#N以下の正の整数の文字列を生成



list_a=np.arange(1, N+1)
list_b =[]


#print(list_a)
#print(len(str(list_a)))

for i in list_a:
    if  len(str(i))%2 !=0:
        #print(i)
        list_b.append(i)

print(len(list_b))
import bisect
import numpy as npy
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
n0 = 0
np = 0
nn = 0
for i in a:
  if i>0:
    np += 1
  elif i == 0:
    n0 += 1
  else:
    nn += 1
kp = (np**2-np+nn**2-nn)//2
k0 = n0*(n-n0)+(n0**2-n0)//2
kn = nn*np
if kn < k <= kn+k0:
  print(0)
  exit()
nls = []
pls = []
for i in range(n):
  if a[i] < 0:
    nls.append(a[i])
  elif a[i] > 0:
    pls.append(a[i])
ln = len(nls)
lp = len(pls)
if k <= kn:
  nls = npy.array(nls,dtype=npy.int32)
  pls = npy.array(pls,dtype=npy.int32)
  l = a[0]*a[-1]-1
  r = 0
  while l+1 < r:
    m = (l+r)//2
    mls = m//nls
    tmp = npy.searchsorted(pls,mls,side="right").sum()
    if tmp > kn-k:
      l = m
    else:
      r = m
  print(l)
else:
  print(2/0)
  """
  l = 0
  r = max(a[0]**2,a[-1]**2)+1
  while l+1 < r:
    m = (l+r)//2
    tmp = 0
    for i in range(ln):
      tmp += 
"""

### FIXED CODE ###

import bisect
import numpy as npy
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
n0,np,nn = 0,0,0
for i in a:
  if i>0:  np += 1
  elif i == 0:  n0 += 1
  else:  nn += 1
kp = (np**2-np+nn**2-nn)//2
k0 = n0*(n-n0)+(n0**2-n0)//2
kn = nn*np
if kn < k <= kn+k0:
  print(0)
  exit()
nls = []
pls = []
for i in range(n):
  if a[i] < 0:
    nls.append(a[i])
  elif a[i] > 0:
    pls.append(a[i])
ln = len(nls)
lp = len(pls)
nls = npy.array(nls,dtype=npy.int64)
pls = npy.array(pls,dtype=npy.int64)
if k <= kn:
  l = a[0]*a[-1]-1
  r = 0
  while l+1 < r:
    m = (l+r)//2
    mls = m//nls
    tmp = npy.searchsorted(pls,mls,side="right").sum()
    if tmp > kn-k:
      l = m
    else:
      r = m
  print(l)
else:
  nls = -nls
  nls = nls[::-1]
  k -= kn+k0
  l = 0
  r = max(a[0]**2,a[-1]**2)+1
  while l+1 < r:
    m = (l+r)//2
    tmp  = npy.searchsorted(nls,m//nls,side="right").sum()
    tmp += npy.searchsorted(pls,m//pls,side="right").sum()
    tmp -= npy.searchsorted(nls**2,m,side="left")
    tmp -= npy.searchsorted(pls**2,m,side="left")
    if tmp >= 2*k:
      r = m
    else:
      l = m
  print(r)