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

n = int(input())
x = []
y = []
h = []
for i in range(n):
    xi,yi,hi = map(int, input().split())
    x.append(xi)
    y.append(yi)
    h.append(hi)


cxyl = []
for i in range(101):
    for j in range(101):
        cxyl.append((i,j))
cxy = set(cxyl)
hd = {}
hzero = []
for i in range(n):
    for c in list(cxy):
        H = abs(x[i]-c[0]) + abs(y[i]-c[1]) + h[i]
        if h[i] == 0:
            hzero.append((x[i],y[i]))
            if 1 > H:
                cxy.remove(c)
                continue
        else:
            if c in hd:
                if hd[c] != H:
                    cxy.remove(c)
                    continue
            else:
                hd[c] = H

for xy in hzero:
    xi = xy[0]
    yi = xy[1]
    for c in list(cxy):
        H = abs(xi-c[0]) + abs(yi-c[1])
        if hd[c] - H > 0:
            cxy.remove(c)

ret = cxy.pop()
print(str(ret[0]) + ' ' + str(ret[1]) + ' ' + str(hd[ret]))


### FIXED CODE ###

n = int(input())
x = []
y = []
h = []
for i in range(n):
    xi,yi,hi = map(int, input().split())
    x.append(xi)
    y.append(yi)
    h.append(hi)


cxyl = []
for i in range(101):
    for j in range(101):
        cxyl.append((i,j))
cxy = set(cxyl)
hd = {}
hzero = set([])
for i in range(n):
    for c in list(cxy):
        H = abs(x[i]-c[0]) + abs(y[i]-c[1]) + h[i]
        if h[i] == 0:
            hzero.add((x[i],y[i]))
            if 1 > H:
                cxy.remove(c)
                continue
        else:
            if c in hd:
                if hd[c] != H:
                    cxy.remove(c)
                    continue
            else:
                hd[c] = H

for xy in list(hzero):
    xi = xy[0]
    yi = xy[1]
    for c in list(cxy):
        H = abs(xi-c[0]) + abs(yi-c[1])
        if hd[c] - H > 0:
            cxy.remove(c)

ret = cxy.pop()
print(str(ret[0]) + ' ' + str(ret[1]) + ' ' + str(hd[ret]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import re
def print_ans(S):
    """Test Case
    >>> print_ans("0011")
    4
    >>> print_ans("11011010001011")
    12
    >>> print_ans("0")
    0
    """
    flg = True
    ans = 0
    while flg:
        tmp = re.sub(r"01|10", "", S)
        if len(tmp) == len(S):
            flg = False
            break
        else:
            ans += len(S) - len(tmp)
            S = tmp
    print(ans)
        


if __name__ == '__main__':
    S = input().rstrip()
    print_ans(S)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import re
def print_ans(S):
    """Test Case
    >>> print_ans("0011")
    4
    >>> print_ans("11011010001011")
    12
    >>> print_ans("0")
    0
    """
    flg = True
    ans = 0
    # while flg:
    #     tmp = re.sub(r"01|10", "", S)
    #     if len(tmp) == len(S):
    #         flg = False
    #         break
    #     else:
    #         ans += len(S) - len(tmp)
    #         S = tmp
    # print(ans)
    list_0 = []
    list_1 = []
    for s in S:
        if s =="0":
            list_0.append(s)
        else:
            list_1.append(s)
    print(min(len(list_0), len(list_1)) * 2)
        


if __name__ == '__main__':
    S = input().rstrip()
    print_ans(S)
### BUGGY CODE ###

N = int(input())
P_lis = list(map(int,input().split()))
 
count = 0
for i in range(N):
  lis = P_lis[0:i+1]
  if lis[i] == min(lis):
    count += 1
print(count)

### FIXED CODE ###

N = int(input())
P_lis = list(map(int, input().split()))
 
dummy = 2*10**5
answer = 0
 
for p in P_lis:
  if p <= dummy:
    answer += 1
    dummy = p
print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n=int(input())
N=[str(i) for i in range(1,n+1)]

count=0
for a in N:
  for b in N:
    if str(a)[0]==str(b)[-1] and str(a)[-1]==str(b)[0]:
      count+=1

print(count)

### FIXED CODE ###

N=int(input())
d=[[0]*10 for i in range(10)]
#10x10のグリッドを作る

#9x9パターンに分類されるため、各数字をグリッドに振り分ける
for i in range(1,N+1):
  n=str(i)
  d[int(n[0])][int(n[-1])]+=1

#組み合わせの数は[Aの数]x[Bの数] 先頭か語尾に0が付くものはカウントしない
r=0
for i in range(9):
  for j in range(9):
    r+=d[i+1][j+1]*d[j+1][i+1]
print(r)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
total = 1
for i in range(n):
    total *= A[i]
if total > 10**18:
    print('-1')
else:
    print(total)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
total = 1
count = 0
for i in range(n):
    total *= A[i]
    if total > 10**18:
        count += 1
        break

if 0 in A:
    print('0')
elif count == 1:
    print('-1')
else:
    print(total)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
lr_list = [list(map(int, input().split())) for i in range(Q)]

for lr in lr_list:
    len_bfr = len(S[lr[0] - 1:lr[1]])
    len_aft = len((S[lr[0] - 1:lr[1]]).replace("AC",""))
    print((len_bfr - len_aft) // 2 )

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
lr_list = [list(map(int, input().split())) for i in range(Q)]

ac_list  = [0]*N
cnt = 0
for i in range(N-1):
    if i < len(S) and S[i:i+2] == "AC":
        cnt += 1
    ac_list[i+1] = cnt
        
for lr in lr_list:
    print(ac_list[lr[1]-1] - ac_list[lr[0]-1])
### BUGGY CODE ###

import math

k = int(input())+1

sum = 0
for a in range(1,k):
    for b in range(1,k):
        for c in range(1,k):
            common = math.gcd(a,b)
            sum += math.gcd(common,c)

print(sum)

### FIXED CODE ###

import math
k = int(input())+1

sum = 0
for a in range(1,k):
    for b in range(a,k):
        for c in range(b,k):
            tmp = math.gcd(math.gcd(a,b),c)

            if a != b and b != c and a != c:
                tmp *= 2
            if a!=b or b!=c:
                tmp *= 3
            sum += tmp

print(sum)
### BUGGY CODE ###

N = int(input())

a, b = 1, 1
for i in range(N):
    T, A = map(int, input().split())
    tmp_T = T
    tmp_A = A
    while True:
        if a <= tmp_T and b <= tmp_A:
            a = tmp_T
            b = tmp_A
            break
        tmp_T += T
        tmp_A += A
        
print(a+b)

### FIXED CODE ###

N = int(input())

a, b = 1, 1
for i in range(N):
    T, A = map(int, input().split())
    mult = max((T+a-1)//T, (A+b-1)//A)
    a, b = T * mult, A * mult
        
print(a+b)
### BUGGY CODE ###

H, W = list(map(int, input().split()))
Hs = [[0] * W for i in range(H)]
Vs = [[0] * W for i in range(H)]

Ss = [0] * H
for i in range(H):
    Ss[i] = input()

# 横
for i in range(H):
    s = 0
    e = 0
    c = 0
    for k in range(W):
        if Ss[i][k] == ".":
            c += 1
        else:
            e = k
            for m in range(e - s):
                Hs[i][s + m] = c
            s = e + 1
            c = 0
    e = W
    for m in range(e - s):
        Hs[i][s + m] = c
# 縦
for i in range(W):
    s = 0
    e = 0
    c = 0
    for k in range(H):
        if Ss[k][i] == ".":
            c += 1
        else:
            e = k
            for m in range(e - s):
                Vs[s + m][i] = c
            s = e + 1
            c = 0
    e = H
    for m in range(e - s):
        Vs[s + m][i] = c

maxv = 0
for i in range(H):
    for k in range(W):
        t = Hs[i][k] + Vs[i][k] - 1
        if t > maxv:
            maxv = t
print(maxv)

### FIXED CODE ###

H, W = list(map(int, input().split()))
Hs = [[0] * W for i in range(H)]
Vs = [[0] * W for i in range(H)]
 
Ss = [0] * H
for i in range(H):
    Ss[i] = input()
 
for i in range(H):
    s = 0
    e = 0
    c = 0
    for k in range(W):
        if Ss[i][k] == ".":
            c += 1
        else:
            e = k
            for m in range(e - s):
                Hs[i][s + m] = c
            s = e + 1
            c = 0
    e = W
    for m in range(e - s):
        Hs[i][s + m] = c
# 縦
for i in range(W):
    s = 0
    e = 0
    c = 0
    for k in range(H):
        if Ss[k][i] == ".":
            c += 1
        else:
            e = k
            for m in range(e - s):
                Vs[s + m][i] = c
            s = e + 1
            c = 0
    e = H
    for m in range(e - s):
        Vs[s + m][i] = c
 
maxv = 0
for i in range(H):
    for k in range(W):
        t = Hs[i][k] + Vs[i][k] - 1
        if t > maxv:
            maxv = t
print(maxv)
### BUGGY CODE ###

import sys
import copy
from collections import deque
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
a = na()

def calc_lux(a):
    res = [0 for _ in range(len(a))]
    cnt = 0
    for i in range(len(a)):
        light = a[i]
        if light==len(a):
            cnt += 1
            continue
        for j in range(max(0, i-light), min(n-1, i+light)+1, 1):
            res[j] += 1
    for i in range(len(res)):
        res[i] += cnt
    return res

for _ in range(k):
    # calc lux from a
    lux = calc_lux(a)

    if a==lux:
        a = lux
        break

    # overwrite a
    a = lux
    # print(lux)

print(" ".join([str(i) for i in a]))

### FIXED CODE ###

import sys
import copy
from collections import deque
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
a = na()

def calc_lux(a):
    imosu = [0 for _ in range(len(a))]
    res = [0 for _ in range(len(a))]
    cnt = 0
    for i in range(len(a)):
        light = a[i]
        le = max(0, i-light)
        imosu[le] += 1
        if i+light < n-1:
            imosu[i+light+1] -= 1

    tmp = 0
    for i in range(len(res)):
        tmp += imosu[i]
        res[i] += tmp
    return res

for _ in range(k):
    # calc lux from a
    lux = calc_lux(a)

    if a==lux:
        a = lux
        break

    # overwrite a
    a = lux
    # print(lux)

print(" ".join([str(i) for i in a]))
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
class Node:
    def __init__(self, sigma, depth):
        self.end = False
        self.child = [None] * sigma
        self.depth = depth
        self.count = 0
    def __setitem__(self, i, x):
        self.child[i] = x
    def __getitem__(self, i):
        return self.child[i]

class Trie():
    def __init__(self, sigma):
        self.sigma = sigma
        self.root = Node(sigma, 0)
    
    def add(self, S):
        vn = self.root
        vn.count += 1
        for cs in S:
            if vn[cs] is None:
                vn[cs] = Node(self.sigma, vn.depth + 1)
            vn = vn[cs]
            vn.count += 1
        vn.end = True

T = Trie(26)
N = int(readline())
Di = [None]*N

for i in range(N):
    S = list(map(lambda x: ord(x)-97, readline().strip()))
    Di[i] = S
    T.add(S)

Q = int(readline())
Ans = [None]*Q
for qu in range(Q):
    k, p = readline().strip().split()
    k = int(k)-1
    p = list(map(lambda x:ord(x)-97, p))
    vn = T.root
    res = 0
    for si in Di[k]:        
        for al in p:
            if al == si:
                break
            if vn[al] is not None:
                res += vn[al].count
        vn = vn[si]
        if vn.end:
            res += 1
    Ans[qu] = res
print('\n'.join(map(str, Ans)))

### FIXED CODE ###

import sys
readline = sys.stdin.readline
class Node:
    def __init__(self, sigma, depth):
        self.end = False
        self.child = [None] * sigma
        self.depth = depth
        self.count = 0
    def __setitem__(self, i, x):
        self.child[i] = x
    def __getitem__(self, i):
        return self.child[i]

class Trie():
    def __init__(self, sigma):
        self.sigma = sigma
        self.root = Node(sigma, 0)
    
    def add(self, S):
        vn = self.root
        vn.count += 1
        for cs in S:
            if vn[cs] is None:
                vn[cs] = Node(self.sigma, vn.depth + 1)
            vn = vn[cs]
            vn.count += 1
        vn.end = True

T = Trie(26)
N = int(readline())
Di = [None]*N

for i in range(N):
    S = list(map(lambda x: ord(x)-97, readline().strip()))
    Di[i] = S
    T.add(S)

Q = int(readline())
Ans = [None]*Q
Query = [[] for _ in range(N)]
for qu in range(Q):
    k, p = readline().strip().split()
    k = int(k)-1
    p = list(map(lambda x:ord(x)-97, p))
    pinv = [None]*26
    for i in range(26):
        pinv[p[i]] = i
    Query[k].append((qu, pinv))

for k in range(N):
    if not Query[k]:
        continue
    cost = [[0]*26 for _ in range(26)]
    geta = 0
    vn = T.root
    for si in Di[k]:        
        for ti in range(26):
            if si != ti and vn[ti] is not None:
                cost[si][ti] += vn[ti].count
        vn = vn[si]
        if vn.end:
            geta += 1
    L, P = map(list, zip(*Query[k]))
    M = len(P)
    for idx in range(M):
        res = 0
        invp = P[idx]
        for i in range(26):
            for j in range(26):
                if invp[i] > invp[j]:
                    res += cost[i][j]
        Ans[L[idx]] = res+geta
        
print('\n'.join(map(str, Ans)))
### BUGGY CODE ###

from functools import lru_cache, reduce
from bisect import bisect
n = int(input())
aa = list(map(int, input().split()))

lencache = []
cache = []

@lru_cache(maxsize=10**9)
def gcd2(a, b) :
    if a%b : return gcd2(b, a%b)
    else : return b

@lru_cache(maxsize=10**9)
def gcdn(fs) :
    global cache, lencache
    l = len(fs)
    i = bisect(lencache, l)
    lencache.insert(i, l)
    cache.insert(i, fs)
    if l == 1 :
        return list(fs)[0]
    elif l < 10 :
        return reduce(gcd2, fs)
    else :
        for c in cache[::-1] :
            if c in fs :
                return gcd2(gcdn(c), gcdn(fs-c))
        else :
            c = frozenset({v for i, v in enumerate(fs) if i<len(fs)/2})
            return gcd2(gcdn(c), gcdn(fs-c))

m = 1
for i in range(n) :
    s = frozenset(aa[:i]+aa[i+1:])
    g = gcdn(s)
    if g > m :
        m = g
else :
    print(m)

### FIXED CODE ###

from functools import lru_cache
n = int(input())
aa = list(map(int, input().split()))

@lru_cache(maxsize=10**9)
def gcd(a, b) :
    if b == 0 : return a
    elif a%b : return gcd(b, a%b)
    else : return b

l = [0]
r = [0]
for i in range(n) :
    l.append(gcd(l[-1], aa[i]))
    r.append(gcd(r[-1], aa[-i-1]))

m = [gcd(l[i],r[-i-2]) for i in range(n)]
print(max(m))
### BUGGY CODE ###

def main():
    from collections import deque

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    vis = set()

    mw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    mj = list(set((i, j) for i in range(-2, 3) for j in range(-2, 3)) - set(mw) - {(0, 0)})

    q = deque()
    q.append((start[0], start[1], 0))
    while q:
        y, x, c = q.popleft()
        if (y, x) in vis or maze[y][x] == '#':
            continue
        vis.add((y, x))
        if (y, x) == goal:
            print(c)
            break
        for a, b in mw:
            if 0 <= y + a < h and 0 <= x + b < w:
                q.appendleft((y + a, x + b, c))
        for a, b in mj:
            if 0 <= y + a < h and 0 <= x + b < w:
                q.append((y + a, x + b, c + 1))
    else:
        print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import deque

    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x) - 1, input().split())
    dh, dw = map(lambda x: int(x) - 1, input().split())

    m = [list(input()) for _ in range(h)]
    vis = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def walk(i, j):
        q = deque()
        q.append((i, j))
        edge = []
        while q:
            y, x = q.popleft()
            if vis[y][x]:
                continue
            vis[y][x] = True
            for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if not 0 <= y + s <= h - 1 or not 0 <= x + t <= w - 1:
                    continue
                if m[y + s][x + t] == '#':
                    edge.append((y, x))
                    continue
                q.appendleft((y + s, x + t))
        return edge

    def jump(i, j, c):
        q = walk(i, j)
        if vis[dh][dw]:
            return c
        nx = []
        c += 1
        while q:
            y, x = q.pop()
            for s in range(-2, 3):
                for t in range(-2, 3):
                    if not 0 <= y + s <= h - 1 or not 0 <= x + t <= w - 1:
                        continue
                    if vis[y + s][x + t]:
                        continue
                    if m[y + s][x + t] == '#':
                        continue
                    nx += walk(y + s, x + t)
                    if vis[dh][dw]:
                        return c
            if len(q) == 0:
                c += 1
                q = nx
                nx = []

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


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

from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -((-t)//A), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
    return (count < K)
        


l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)
### BUGGY CODE ###

#5618213
n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)
  
for b,c in bc:
  a.extend([c]*b)
a.sort(reverse=True)
print(sum(a[:n]))


### FIXED CODE ###

from heapq import heappush, heappop
from operator import itemgetter
N, K = map(int, input().split())
x = list(map(int, input().split()))
t = []
for i in range(K):
    ta, tb = map(int, input().split())
    t.append([ta,tb]) 
a = sorted(t, key=itemgetter(1))
x.sort()
x = x[::-1]
s = 0
l = []
while x or a:
    if a[-1][0] == 0:a.pop()
    if not a:
        s+=sum(x)
        break
    if len(x) ==0:break
    r = x.pop()
    if r < a[-1][1]:
        s+=a[-1][1]
        a[-1][0]-=1
    else:
        s+=sum(x)+r
        break
print(s)
### BUGGY CODE ###

n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
l = len(imos)
imos.sort()
for i in range(q):
    d = int(input())
    while j < l:
        now,stop = imos[j]
        if now > d:
            break
        if stop > 0:
            ans.add(stop)
        else:
            ans.remove(-stop)
        j += 1
    if ans:
        print(min(ans))
    else:
        print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
for i in range(q):
    d = int(input())
    imos.append((d,1e100))
imos.sort()
m = 1e100
flag = False
for t,stop in imos:
    if stop == 1e100:
        if ans:
            if not flag:
                m = min(ans)
                flag = True
            print(m)
        else:
            print(-1)
    elif stop > 0:
        ans.add(stop)
        if stop < m:
            m = stop
            flag = True
    else:
        ans.remove(-stop)
        if m == -stop:flag = False
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
aset=list(set(a))
ans=0
alist=[ 0 for i in range(n)]
for j in aset:
    k=a.count(j)
    alist[j-1]=k
    ans+=(k*(k-1))//2
for u in a:
    print(ans-alist[u-1]+1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
aset=list(set(a))
ans=0
al=[0]*200000
for i in a:
    al[i]+=1
for j in aset:
    k=al[j]
    ans+=(k*(k-1))//2
for u in a:
    print(ans-al[u]+1)
### BUGGY CODE ###

n,k=map(int,input().split())
l=[0]*(k+1)
for i in range(k):
    num=(k-i)
    if k//num==1:
        l[num]=1
    else:
        ret=((k//num)**n)%(10**9+7)
        for j in range(2,k//num+1):
            ret-=l[num*j]
            ret%=(10**9+7)
        l[num]=(ret)%(10**9+7)
ans=0
for i in range(k+1):
    ans+=(l[i]*i)%(10**9+7)
print(ans%(10**9+7))


### FIXED CODE ###

n,k=map(int,input().split())
l=[0]*(k+1)
for i in range(k):
    num=(k-i)
    if k//num==1:
        l[num]=1
    else:
        ret=pow(k//num,n,10**9+7)
        for j in range(2,k//num+1):
            ret-=l[num*j]
            ret%=(10**9+7)
        l[num]=(ret)%(10**9+7)
ans=0
for i in range(k+1):
    ans+=(l[i]*i)%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

import sys
bbn=1000000007
	
#+++++

def modinv(a,m):
	b=m
	u=1
	v=0
	
	while b > 0:
		t = a //b
		a = a - (t * b)
		a,b = b,a
		u = u - (t * v)
		u,v=v,u
	
	u = u % m
	if u < 0:
		u+=m
	return u

def gcd(a,b):
	while b!= 0:
		a,b=b,a%b
		
	return a
		
def main():
	n = int(input())
	al = list(map(int, input().split()))
	
	#saisyoukoubausuu
	ss=1
	for v in al:
		ss = ss * v //gcd(ss,v)
		#ss %= bbn
	
	#ss=ss%bbn
	ret=0
	for v in al:
		ret += ss // v
		ret%=bbn
		
	
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
bbn=1000000007
	
#+++++

def modinv(a,m):
	b=m
	u=1
	v=0
	
	while b > 0:
		t = a //b
		a = a - (t * b)
		a,b = b,a
		u = u - (t * v)
		u,v=v,u
	
	u = u % m
	if u < 0:
		u+=m
	return u

def gcd(a,b):
	while b!= 0:
		a,b=b,a%b
		
	return a
		
def main():
	n = int(input())
	al = list(map(int, input().split()))
	
	#saisyoukoubausuu
	ss=1
	for v in al:
		ss = ss * v //gcd(ss,v)
		#ss %= bbn
	
	ss=ss%bbn
	ret=0
	for v in al:
		ret += ss *modinv(v, bbn)
		ret%=bbn
		
	
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))

m = []
for i in range(n):
    m.insert(bisect_left(m, a[i]), a[i])
    b = [a[i]]
    c = 1
    for r in range(i + 1, n):
        b.insert(bisect_left(b, a[r]), a[r])
        c += 1
        temp = b[c // 2]
        m.insert(bisect_left(m, temp), temp)

print(m[((n + 1) * n) // 4])


### FIXED CODE ###

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

if n == 1:
    print(a[0])
    exit()

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n + 2) ]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])