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

from collections import deque

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

graphs = [[[] for _ in range(n)], [[] for _ in range(n)]]
cands = [set(), set()]
for _ in range(k):
    x, y = map(int, input().split())
    graphs[0][x - 1].append(y - 1)
    graphs[0][y - 1].append(x - 1)
    cands[0].add(x - 1)
for _ in range(l):
    x, y = map(int, input().split())
    graphs[1][x - 1].append(y - 1)
    graphs[1][y - 1].append(x - 1)
    cands[1].add(x - 1)

groups = [[], []]
groups_inv = [[-1] * n, [-1] * n]
def dfs(start, size, type, num):
    q = deque(maxlen=size)
    q.append(start)
    used = {start}
    groups[type].append(used)
    groups_inv[type][start] = num
    while q:
        node = q.popleft()
        for to in graphs[i][node]:
            if to in used:
                continue
            q.append(to)
            used.add(to)
            groups_inv[type][to] = num

for i in range(2):
    count = 0
    for node in cands[i]:
        if groups_inv[i][node] == -1:
            dfs(node, n, i, count)
            count += 1

print(*[
    1 if groups_inv[0][i] == -1 or groups_inv[1][i] == -1
    else len(groups[0][groups_inv[0][i]] & groups[1][groups_inv[1][i]])
    for i in range(n)
])


### FIXED CODE ###

from collections import deque

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

graphs = [[[] for _ in range(n)], [[] for _ in range(n)]]
cands = [set(), set()]
for _ in range(k):
    x, y = map(int, input().split())
    graphs[0][x - 1].append(y - 1)
    graphs[0][y - 1].append(x - 1)
    cands[0].add(x - 1)
for _ in range(l):
    x, y = map(int, input().split())
    graphs[1][x - 1].append(y - 1)
    graphs[1][y - 1].append(x - 1)
    cands[1].add(x - 1)

groups = [[], []]
groups_inv = [[-1] * n, [-1] * n]
def dfs(start, case, num):
    q = deque()
    q.append(start)
    used = {start}
    groups[case].append(used)
    groups_inv[case][start] = num
    while q:
        node = q.popleft()
        for to in graphs[case][node]:
            if to in used:
                continue
            q.append(to)
            used.add(to)
            groups_inv[case][to] = num

for i in range(2):
    count = 0
    for node in cands[i]:
        if groups_inv[i][node] == -1:
            dfs(node, i, count)
            count += 1

ret = [-1] * n
for i in range(n):
    if groups_inv[0][i] == -1 or groups_inv[1][i] == -1:
        ret[i] = 1
    elif ret[i] == -1:
        cities = groups[0][groups_inv[0][i]] & groups[1][groups_inv[1][i]]
        for city in cities:
            ret[city] = len(cities)
print(*ret)
### BUGGY CODE ###

d,g=map(int,input().split())
p=[]
c=[]
for i in range(d):
    p1,c1=map(int,input().split())
    p.append(p1)
    c.append(c1//100)
ans=1100
g//=100
import itertools
n=list(itertools.permutations(list(range(1,d+1))))
for i in range(len(n)):
    cnt=g
    cnt2=0
    for j in range(d):
        if cnt2>=ans:
            break
        num3=n[i][j]
        num4=num3*p[num3-1]
        if num4>=cnt:
            cnt2+=((cnt-1)//num3)+1
            break
        elif num4+c[num3-1]>=cnt:
            cnt2+=p[num3-1]
            break
        cnt-=num4+c[num3-1]
        cnt2+=p[num3-1]
    ans=min(ans,cnt2)
print(ans)


### FIXED CODE ###

import itertools
d,g=map(int,input().split())
p=[]
c=[]
for i in range(d):
    p1,c1=map(int,input().split())
    p.append(p1)
    c.append(c1//100)
n=list(itertools.permutations(list(range(1,d+1))))
ans=1024
g//=100
for i in range(len(n)):
    cnt=g
    cnt2=0
    for j in range(d):
        num3=n[i][j]
        num4=num3*p[num3-1]
        if num4>=cnt:
            cnt2+=((cnt-1)//num3)+1
            break
        elif num4+c[num3-1]>=cnt:
            cnt2+=p[num3-1]
            break
        else:
            cnt-=num4+c[num3-1]
            cnt2+=p[num3-1]
    ans=min(ans,cnt2)
print(ans)
### BUGGY CODE ###

N = 0
V = []
C = []
 
i = 0
ans = 0

str = input()
N = int(str)
 
str = input().split()
while i < N:
  V.append(int(str[i]))
  i = i+1
  
i=0
str = 0
str = input().split()
while i < N:
  C.append(int(str[i]))
  i = i+1

i=0
while i<N:
  if V[i] > C[i]:
    ans = ans + V[i] - C[i]
    i = i+1
    
    
print(ans)

### FIXED CODE ###

N = 0
V = []
C = []
 
i = 0
ans = 0

str = input()
N = int(str)
 
str = input().split()
while i < N:
  V.append(int(str[i]))
  i = i+1
  
i=0
str = 0
str = input().split()
while i < N:
  C.append(int(str[i]))
  i = i+1

i=0
while i<N:
  if V[i] > C[i]:
    ans = ans + V[i] - C[i]
  i = i+1
    
    
print(ans)
### BUGGY CODE ###

import copy

N,K = map(int, input().split())
*P, = map(int, input().split())
*C, = map(int, input().split())

P2 = copy.deepcopy(P)

ans = 0
while P2:
    count = K
    ans_tmp = 0
    s = P2.pop()
    while count:
        ans_tmp += C[s-1]
        count -= 1
        s = P[s-1]
        ans = max(ans, ans_tmp)

if ans == 0:
    print(max(C))
else:
    print(ans)


### FIXED CODE ###

"""
解説動画のコードを参考にしました
https://atcoder.jp/contests/abc175/submissions/15945829
"""

N,K = map(int, input().split())
*P, = map(int, input().split())
*C, = map(int, input().split())

ans = int(-1e18)

for start in P:
    pos = start
    scores = [] # スコア格納用

    while True:
        pos = P[pos-1] # 移動
        scores.append(C[pos-1]) # スコアの格納
        # 1周したかどうか
        if pos == start: break

    # 周期途中のどこでやめるか判定
    L = len(scores)
    S = sum(scores)
    period_score = 0
    for i in range(L):
        period_score += scores[i] # スコアの加算
        # 試行回数を超えていないか
        if i+1 > K: break
        total_score = period_score
        # 1周期の合計スコアが正なら、周期を重ねるごとにスコア増
        if S > 0:
            total_score += S * ((K-(i+1)) // L)
        ans = max(ans, total_score)

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

import collections
N = int(input())
a = list(map(int, input().split()))
a_c = collections.Counter(a)
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]
S = [0]*Q

for i, bc in enumerate(BC):
  b = bc[0]
  c = bc[1]
  s = 0
  if b in a_c:
    a_c[c]+=a_c.pop(b)
  for k, v in a_c.items():
    s += k*v
  S[i] = s

[print(i) for i in S]

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int, input().split()))
a_c = collections.Counter(a)
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]
s_old = 0
for k, v in a_c.items():
    s_old += k*v
for bc in BC:
  b = bc[0]
  c = bc[1]
  s = s_old
  if b in a_c:
    n = a_c.pop(b)
    a_c[c]+=n
    s-=n*b
    s+=n*c
  print(s)
  s_old = s
### BUGGY CODE ###

H,W = map(int,input().split())
S_X=[]
S_Y=[]
C_X=[]
C_Y=[]
ans_list=[]
B = []

for i in range(H):
    A = list(input())
    for j in range(W):
        if A[j] == '#':
            S_X.append(i+1)
            S_Y.append(j+1)
        else :
            C_X.append(i+1)
            C_Y.append(j+1)

S_len=len(S_X)
C_len=len(C_X)


for i in range(C_len):
    for j in range(S_len):
        B.append((abs(S_X[j]-C_X[i])+abs(S_Y[j]-C_Y[i])))
    a = min(B)*(-1)
    ans_list.append(a)
    
    B = []

ans_list.sort()

if C_len == 0:
    print(0)
else:
    print(ans_list[0]*(-1))


### FIXED CODE ###

import numpy as np

H,W=map(int,input().split())
max_value = H+W
matrix =[]

for _ in range(H):
    matrix.append([0 if i == '#' else max_value for i in list(input())])
matrix = np.array(matrix)

for c in range(W-1):
    matrix[:,c+1] = np.minimum(matrix[:,c]+1,matrix[:,c+1])
for c in range(W-1,0,-1):
    matrix[:,c-1] = np.minimum(matrix[:,c-1],matrix[:,c]+1)
for r in range(H-1):
    matrix[r+1,:] = np.minimum(matrix[r,:]+1,matrix[r+1,:])
for r in range(H-1,0,-1):
    matrix[r-1,:] = np.minimum(matrix[r,:]+1,matrix[r-1,:])


print(np.max(matrix))
### BUGGY CODE ###

t = input()

#print(t[-1])

ans = ''

if t[-1] == '?':
  ans += 'D'
else:
  ans += t[-1]
#print(t)
#print(ans)

for i in range(-2, -len(t)-1, -1):
  #print(i, t[i])
  if t[i] == '?':
    if t[i+1] == 'P':
      ans += 'D'
    else:
      ans += 'P'
  else:
    ans += t[i]
#print(ans)
print(ans[::-1])

### FIXED CODE ###

t = input()
ans = list(t)

if ans[-1] == '?':
  ans[-1] = 'D'

tl = len(t)
for i in range(-2, -tl-1, -1):
  if ans[i] == '?':
    if ans[i+1] == 'P':
      ans[i] = 'D'
    else:
      if i != -tl and ans[i-1] == 'P':
        ans[i] = 'D'
      else:
        ans[i] = 'P'
print(''.join(ans))
### BUGGY CODE ###

import math

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

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

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

if gcd(A,B)==1:
    print(1)
else:
    N=gcd(A,B)
    P = [2]
    flag = 0
    for i in range(3,N+1,2):
        for j in range(len(P)):
            if math.sqrt(i) < P[j]:
                break
            else:
                if i%P[j] == 0:
                    flag += 1
                    break
        if flag == 0:
            P.append(i)
        flag = 0
    P.append(1)
    ans=0
    y=yakusuu(N)
    for i in range(len(y)):
        if y[i] in P:
            ans+=1
    print(ans)

### FIXED CODE ###

import collections

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A,B=map(int, input().split())
N=gcd(A,B)
c = collections.Counter(prime_factorize(N))
print(len(list(c.keys()))+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))


count =0

while(not a==[]):
    am = min(a)
    c = a.count(am)
    a = [j for j in a if not j %am ==0]
    if c ==1:
        count =count +1

print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]



for i in a:
    ac[i] +=1
a = sorted(set(a))
count =0

for i in a:
    if ac[i]>0:
        if ac[i] == 1:
            count += 1
        for j in range(i,10**6+2,i):
            if not ac[j]==0:
                ac[j]=0


print(count)
### BUGGY CODE ###

s = input()
mod = 10**9 + 7
if s[-1]=="?":
    dp = [1]*13
    dp[10:13] = [0,0,0]
else:
    dp = [0]*13
    dp[int(s[-1])] = 1
if len(s)==1:
    print(dp[5])
    exit()
else:
    mul = 10
    for i in reversed(range(len(s)-1)):
        nextdp = [0] * 13
        if s[i]=="?":
            for j in range(10):
                for k in range(13):
                    l = (j*mul+k) % 13
                    nextdp[l] += dp[k]
        else:
            for k in range(13):
                l = (int(s[i])*mul+k) % 13
                nextdp[l] += dp[k]
        mul *= 10
        dp = nextdp
    print(dp[5]%mod)
    exit()

### FIXED CODE ###

s = input()
mod = 10**9 + 7
N = len(s)
if s[-1]=="?":
    dp = [1]*13
    dp[10:13] = [0,0,0]
else:
    dp = [0]*13
    dp[int(s[-1])] = 1
if N==1:
    print(dp[5])
    exit()
else:
    mul = 10
    for i in reversed(range(N-1)):
        nextdp = [0] * 13
        if s[i]=="?":
            for j in range(10):
                for k in range(13):
                    l = (j*mul+k) % 13
                    nextdp[l] += dp[k]
                    nextdp[l] %= mod
        else:
            for k in range(13):
                l = (int(s[i])*mul+k) % 13
                nextdp[l] += dp[k]
                nextdp[l] %= mod
        mul *= 10
        mul %= 13
        dp = nextdp
    print(dp[5])
    exit()
### BUGGY CODE ###

S = input()
N = len(S)
while "01" in S or "10" in S:
	S = S.replace("10", "").replace("01", "")
print(N - len(S))


### FIXED CODE ###

S = input()
One = S.count("1")
Zero = S.count("0")
print(len(S) - max(One, Zero) + min(One, Zero))
### BUGGY CODE ###

A, B = map(int, input().split())
ans = A
for i in range(A+1, B+1):
    ans = ans ^ i
print(ans)


### FIXED CODE ###

A, B = map(int, input().split())
A -= 1
ak, amod = divmod(A, 4)

cum_a = 0
if amod == 0:
    cum_a = A
elif amod == 1:
    cum_a = 1
elif amod == 2:
    cum_a = 4*ak + 3
else:
    cum_a = 0

bk, bmod = divmod(B, 4)
cum_b = 0
if bmod == 0:
    cum_b = B
elif bmod == 1:
    cum_b = 1
elif bmod == 2:
    cum_b = 4*bk + 3
else:
    cum_b = 0

print(cum_a ^ cum_b)
### BUGGY CODE ###

from collections import defaultdict

def main():
    S = input()
    d = defaultdict(int)
    d[0] = 1

    num = 0
    for digit, c in enumerate(S[::-1]):
        num += int(c) * 10 ** digit
        rem = num % 2019
        d[rem] += 1
    ans = sum([d[i]*(d[i]-1)//2 for i in range(2019)])
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict

def main():
    S = input()
    d = defaultdict(int)
    d[0] = 1

    num = 0
    for digit, c in enumerate(S[::-1]):
        num += int(c) * pow(10, digit, 2019)
        num %= 2019
        d[num] += 1
    ans = sum([d[i]*(d[i]-1)//2 for i in range(2019)])
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
l=[0 for _ in range(n)]
id=0
frac=[1 for _ in range(10**5+10)]
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
N=n+1
short=N-(max(buf)-min(buf))

#print(short,N)

for i in range(1,n+2,1):
    if short-i<0:
        sub1=0
    else:
        sub1 = (((frac[short] * modinv(frac[i], p)) % p) * modinv(frac[short - i], p)) % p

    if short-i-1<0:
        sub2=0
    else:
        sub2 = (((frac[short - 1] * modinv(frac[i], p)) % p) * modinv(frac[short - i - 1], p)) % p
    all=(((frac[N]*modinv(frac[i],p))%p)*modinv(frac[N-i],p))%p

    #print(all,sub1,sub2)
    print(((all-sub1)%p+sub2)%p)

### FIXED CODE ###

import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
id=0
frac=[1]*(10**5+10)
fracinv=[0]*(10**5+10)
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
for i in range(0,10**5+10):
    fracinv[i]=modinv(frac[i],p)
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
N=n+1
short=N-(max(buf)-min(buf))

#print(short,N)

for i in range(1,n+2,1):
    if short-i<0:
        sub1=0
    else:
        sub1 = (((frac[short] * fracinv[i]) % p) * fracinv[short-i]) % p

    if short-i-1<0:
        sub2=0
    else:
        sub2 = (((frac[short - 1] * fracinv[i]) % p) * fracinv[short - i - 1]) % p
    all=(((frac[N]*fracinv[i])%p)*fracinv[N-i])%p

    #print(all,sub1,sub2)
    print((all-(sub1-sub2)%p)%p)
### BUGGY CODE ###

s = input().split("T")
x,y = map(int,input().split())
xmove = []
ymove = []
for i in range(1,len(s)):
    if i % 2 == 0:
        xmove.append(s[i].count("F"))
    else:
        ymove.append(s[i].count("F"))
dpx = [[False]*(16001) for i in range(len(xmove)+1)]
dpy = [[False]*(16001) for i in range(len(ymove)+1)]
dpx[0][s[0].count("F")+8000] = True
dpy[0][8000] = True
for i in range(len(xmove)):
    for j in range(16001):
        if dpx[i][j]:
            if 0<=j-xmove[i]:
                dpx[i+1][j-xmove[i]] = True
            if j+xmove[i] <= 16001:
                dpx[i+1][j+xmove[i]] = True
for i in range(len(ymove)):
    for j in range(16001):
        if dpy[i][j]:
            if 0<=j-ymove[i]:
                dpy[i+1][j-ymove[i]] = True
            if j+ymove[i] <= 16001:
                dpy[i+1][j+ymove[i]] = True

if dpx[len(xmove)][x+8000] and dpy[len(ymove)][y+8000]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input().split("T")
x,y = map(int,input().split())
xmove = []
ymove = []
for i in range(len(s)):
    if i % 2 == 1:
        ymove.append(s[i].count("F"))
    else:
        xmove.append(s[i].count("F"))
#リストで持つdpだとTLEしたのでメモ化再帰で書く

def solve(l,cor):
    dp = {0}
    for c in l:
        dp = {c+i for i in dp}|{i-c for i in dp}
    return cor in dp

if solve(xmove[1:],x-xmove[0]) and solve(ymove,y):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n = int(input())
l = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        down = l[j] - l[i]
        up = l[j] + l[i]
        for k in range(j+1,n):
            if down < l[k]:
                if l[k] < up:
                    cnt += 1
                else:
                    break
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        up = l[j] + l[i]
        #l[k] = up となるようなkのうち最小のものを見つけろ
        k = bisect.bisect_left(l, up)
        cnt += k - j - 1
print(cnt)
### BUGGY CODE ###

n = int(input())
G = [[] for i in range(n)]
root = 0
color_num = 0
keys = []

def get_key(n1, n2):
  if n1 > n2:
    return str(n2) + '-' + str(n1)
  return str(n1) + '-' + str(n2)

for _ in range(n - 1):
  a, b = map(int, input().split())
  keys.append(get_key(a - 1, b - 1))
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  if color_num < len(G[a - 1]):
    root = a - 1
    color_num = len(G[a - 1])
  elif color_num < len(G[b - 1]):
    root = b - 1
    color_num = len(G[b - 1])

# print(G)
# [[1], [0, 2, 3, 4], [1], [1, 6], [1, 5], [4, 7], [3], [5]]
# print(root) # 最も多い色を持つノードの番号
print(color_num)  # 必要な最小色数
queue = [root]
checked = set()
result = {}

min_colors = [set(range(color_num)) for i in range(n)]

while len(queue) > 0:
  node = queue.pop(0)
  # print(node + 1)
  # ks = list(range(color_num))
  # print(node)
  # print(ks)
  # for node2 in G[node]:
  #   key = get_key(node, node2)
  #   if key in result:
  #     ks.pop(result[key])
  for node2 in G[node]:
    if node2 not in checked:
      key = get_key(node, node2)
      # result[key] = ks.pop(0)
      result[key] = min_colors[node].pop()
      min_colors[node2].discard(result[key])
      queue.append(node2)
  checked.add(node)

for k in keys:
  print(result[k] + 1)


### FIXED CODE ###

n = int(input())
G = [[] for i in range(n)]
root = 0
color_num = 0

for i in range(n - 1):
  a, b = map(int, input().split())
  G[a - 1].append((b - 1, i))
  G[b - 1].append((a - 1, i))
  if color_num < len(G[a - 1]):
    root = a - 1
    color_num = len(G[a - 1])
  elif color_num < len(G[b - 1]):
    root = b - 1
    color_num = len(G[b - 1])

# print(G)
# [[1], [0, 2, 3, 4], [1], [1, 6], [1, 5], [4, 7], [3], [5]]
# print(root) # 最も多い色を持つノードの番号
print(color_num)  # 必要な最小色数
queue = [(root, -1)]
checked = set()
answer = [-1] * (n - 1)

while len(queue) > 0:
  node, c = queue.pop(0)
  color = 1
  for node2, index in G[node]:
    if node2 not in checked:
      if color == c:
        color = c + 1
      answer[index] = color
      color += 1
      queue.append((node2, answer[index]))
  checked.add(node)
print('\n'.join(map(str, answer)))
### BUGGY CODE ###

l, r = map(int, input().split())

ans_list = []
for i in range(2 * 10**9):
  if l + 1 > r:
    break
  ans = (l * (l + 1)) % 2019
  ans_list.append(ans)
  if ans == 0:
    break
print(min(ans_list))

### FIXED CODE ###

l, r = map(int, input().split())

ans_list = []
for i in range(l, min(l+2019, r)):
  for j in range(i + 1, min(i + 2019, r + 1)):
    ans = (i * j) % 2019
    ans_list.append(ans)
    if ans == 0:
      break
print(min(ans_list))
### BUGGY CODE ###

S = input()
Q = int(input())

for i in range(Q):
    tmp_Q = input().split()

    if len(tmp_Q) == 1:
        S = S[::-1]
    else:
        if tmp_Q[1] == "1":
            S = tmp_Q[2] + S
        else:
            S = S + tmp_Q[2]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())

is_reversed = False
head = ""

for i in range(Q):
    tmp_Q = input().split()

    if len(tmp_Q) == 1:
        is_reversed = not is_reversed
        
    else:
        if tmp_Q[1] == "1":
            if is_reversed:
                S = S + tmp_Q[2]
            else:
                head = head + tmp_Q[2]
        else:
            if is_reversed:
                head = head + tmp_Q[2]
            else:
                S = S + tmp_Q[2]

if is_reversed:
    print(S[::-1] + head)
else:
    print(head[::-1] + S)
### BUGGY CODE ###

class BIT:
    """1-indexed BIT
    """

    def __init__(self, size: int):
        """サイズを指定して BIT を初期化します。
        """
        # BIT のサイズは 2^n + 1
        self.__size = size

        # 実際の配列
        self.__bit = [0] * (self.__size+1)

    def add(self, idx: int, val: int):
        """位置 idx (1-indexed) に値 val をたす。
        :param idx: 値を追加したいインデックス
        :param val: 追加したい値
        """
        while idx <= self.__size:
            self.__bit[idx] += val
            idx += idx & (-idx)

    def sum(self, l: int, r: int)->int:
        """(l, r] の累積和を計算する。
        :param l: left index
        :param r: right index
        :return: (l, r] の累積和
        """
        return self.__sum__(r) - self.__sum__(l)

    def __sum__(self, idx: int)->int:
        s = 0
        while idx > 0:
            s += self.__bit[idx]
            idx -= idx & (-idx)
        return s


def inversion(A: list) -> int:
    bit = BIT(max(A))
    s = 0
    for a in A:
        s += bit.sum(0, a)
        bit.add(a, 1)

    return s


def check(A: list, x: int)->int:
    n = len(A)
    S = [0] * (n + 1)
    for i in range(n):
        if x <= A[i]:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    m = min(S)
    return inversion([s - (m - 1) for s in S])


def median_of_medians(N: int, A: list)->int:
    alpha = sorted(A)
    l, r = 0, N
    while r - l > 1:
        m = (r + l + 1) // 2
        if 2*check(A, alpha[m]) >= (N * (N + 1)) // 2:
            l = m
        else:
            r = m

    return alpha[l]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)


### FIXED CODE ###


def median_of_medians(N: int, A: list)->int:
    def search(c):
        bar = N
        r = 0
        res_nega = 0
        dp_arr = [0]*(2*N+1)
        for i in range(N):
            dp_arr[bar] += 1
            if A[i] < c:
                r += dp_arr[bar]
                bar += 1
            else:
                r -= (dp_arr[bar-1])
                bar -= 1
            res_nega += r
        return res_nega

    # binary search
    a_sorted = sorted(A)
    left = 0
    right = N
    mid = N // 2
    C = N*(N+1) // 2
    while True:
        if search(a_sorted[mid]) <= C // 2:
            if mid == N-1:
                break
            elif search(a_sorted[mid+1]) > C // 2:
                break
            else:
                left = mid
                mid = (mid + right) // 2
        else:
            right = mid + 1
            mid = (mid + left) // 2

    return a_sorted[mid]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)
### BUGGY CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += gcd(i+1, j+1, k+1)
print(ans)

### FIXED CODE ###

import math
from functools import reduce
import itertools


def gcd(*numbers):
    return reduce(math.gcd, numbers)


K = int(input())
l = list(range(1, K + 1))
ans = K * (K + 1) // 2
for i in itertools.combinations(l, 2):
    ans += 3*(gcd(i[0], i[0], i[1])+gcd(i[0], i[1], i[1]))
for i in itertools.combinations(l, 3):
    ans += 6*gcd(i[0], i[1], i[2])

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

from itertools import combinations
n = int(input())
l = list(map(int,input().split()))
ans = 0
for i in combinations(l,3):
    if abs(i[1] - i[2]) < i[0] and i[1] + i[2] > i[0]:
        ans += 1
print(ans)

### FIXED CODE ###

#(0)入力環境
import bisect#listをsortしたまま要素を挿入できる
n = int(input())
l = sorted(list(map(int,input().split())))

#(1)考察
#aとbの二重ループのなかで最後の一つは二分探索で高速に
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        ans += bisect.bisect_left(l,l[i] + l[j]) - (j + 1)
        

print(ans)