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

# https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_d
# D - Crossing

N=int(input())
a=set()
b={}

for i in range(1000):
    if i*(i+1)%2==0:
        s= i*(i+1)//2
        if s<=10**5:
            a.add(s)
            b[s]=i
        else:
            break
            
if N not in a:
    print("No")
else:
    print("Yes")
    print(b[N]+1)
    r=[0 for _ in range(N)] #kaisuu
    t=[ [] for _ in range(b[N]+1)]
    for i in range(b[N]):
        r[i] +=1
    t[0]= [i+1 for i in range(b[N])]
    print(b[N],*t[0])

    for i in range(1,b[N]+1):
        for j in range(i):
            for k,num in enumerate(t[j]):
                if r[num-1]==1:
                    t[i].append(num)
                    r[num-1]+=1
                    break
        for k in range(N):
            if r[k]==0:
                r[k] +=1
                t[i].append(k+1)
                if len(t[i])>=b[N]:
                    break
        print(b[N],*t[i])

        
        
        
        
        #print("i=",i)
        #print(r)
#        for j,num in enumerate(r):
#            if num==1:
#                t[i].append(j+1)
#                r[j]+=1
#                break
        #print("t",t)
        #print(r)
#        for k,num in enumerate(r):
#            if num==0:
#                t[i].append(k+1)
#                r[k]+=1
#            if len(t[i])==b[N]:   
#                break
#        else:
#            pass
#        print(b[N],*t[i])

### FIXED CODE ###

# https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_d
# D - Crossing

N=int(input())
a=set()
b={}

for i in range(1000):
    if i*(i+1)%2==0:
        s= i*(i+1)//2
        if s<=10**5:
            a.add(s)
            b[s]=i
        else:
            break
            
if N not in a:
    print("No")
else:
    print("Yes")
    print(b[N]+1)
    r=[0 for _ in range(N)] #kaisuu
    t=[ [] for _ in range(b[N]+1)]
    for i in range(b[N]):
        r[i] +=1
    t[0]= [i+1 for i in range(b[N])]
    print(b[N],*t[0])

    for i in range(1,b[N]+1):
        for j in range(i):
            for k,num in enumerate(t[j]):
                if r[num-1]==1:
                    t[i].append(num)
                    r[num-1]+=1
                    break
        for k in range(N):
            if r[k]==0:
                r[k] +=1
                t[i].append(k+1)
                if len(t[i])>=b[N]:
                    break
        print(b[N],*t[i])

        
        
        
        
        #print("i=",i)
        #print(r)
#        for j,num in enumerate(r):
#            if num==1:
#                t[i].append(j+1)
#                r[j]+=1
#                break
        #print("t",t)
        #print(r)
#        for k,num in enumerate(r):
#            if num==0:
#                t[i].append(k+1)
#                r[k]+=1
#            if len(t[i])==b[N]:   
#                break
#        else:
#            pass
#        print(b[N],*t[i])
### BUGGY CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))
if N >= M:
    print(0)
else:
    X = sorted(X)
    L = []
    for i in range(0, M-1):
        L.append(X[i+1] - X[i])
        L = sorted(L, reverse = True)
        S = 0
    for i in range(N-1):
        S += L[i]
    res = X[M-1] - X[0] - S
    print(res)


### FIXED CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))
if N >= M:
    print(0)
else:
    X = sorted(X)
    L = []
    for i in range(0, M-1):
        L.append(X[i+1] - X[i])
    L = sorted(L, reverse = True)
    S = 0
    for i in range(N-1):
        S += L[i]
    res = X[M-1] - X[0] - S
    print(res)
### BUGGY CODE ###

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

ans = 1
for i in a:
  ans *= i
  
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

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

def lb_str(a, K):
    n = len(a)
    if n == 0:
        return -1
    elif K <= a[0]:
        return -1
    low = 0
    high = n - 1
    while low < high:
        mid = (low + high + 1) // 2
        if a[mid] < K:
            low = mid
        else:
            high = mid - 1

    return low

N, M = [int(x) for x in input().split()]
A = sorted([int(x) for x in input().split()])

data = []
for i in range(M):
    B, C = [int(x) for x in input().split()]
    data.append([C, B])
data = sorted(data)

for i in range(M):
    C, B = data[i][0], data[i][1]
    j = lb_str(A, C)
    if j + 1 <= B:
        A = [C]*(j + 1) + A[j + 1:]
    else:
        A = A[B:j + 1] + [C]*B + A[j + 1:]
ans = sum(A)
print(ans)


### FIXED CODE ###

N, M = [int(x) for x in input().split()]
A = sorted([int(x) for x in input().split()])

data = []
for i in range(M):
    B, C = [int(x) for x in input().split()]
    data.append([C, B])
data = sorted(data, reverse=True)

D = []
i, tot = 0, 0
while tot < N and i < M:
    C, B = data[i][0], data[i][1]
    for _ in range(B):
        D.append(C)
        tot += 1
        if tot >= N:
            break
    i += 1

i = 0
while i < min(N, len(D)) and A[i] < D[i]:
    i += 1

ans = sum(D[:i] + A[i:])
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np
import itertools

H,W = map(int,readline().split())
S = (np.frombuffer(read(),dtype='S1')==b'#').reshape(H,-1)[:,:W].astype(np.int64)

# pad_width
p = min(H,W)+1

S = np.pad(S,(p,p),'constant').astype(np.int64)

def F(S,H,W):
    # L,Uに頂点があって、RDに第3の頂点がある場合。
    # Rは数えずDだけ数えておく
    cnt = 0
    diag = np.zeros((H+p+p,W+p+p),np.int64)
    for n in range(p,H+p+p):
        diag[n,:-1] = diag[n-1,1:] + S[n,:-1] * 1
    for h,w in itertools.product(range(p,H+p),range(p,W+p)):
        n = min(h-p,w-p)
        L = S[h,w-1:w-n-1:-1]
        U = S[h-1:h-n-1:-1,w]
        RD = diag[h+1:h+n+1,w] - diag[h,w+1:w+n+1]
        cnt += (L*U*RD).sum()
    return cnt

x = []
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))
S = S.T[::-1,:] # 90度回転
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))

answer = sum(x)
print(answer)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np
import itertools

H,W = map(int,readline().split())
S = (np.frombuffer(read(),dtype='S1')==b'#').reshape(H,-1)[:,:W].astype(np.int64)

# pad_width
p = min(H,W)+1

S = np.pad(S,(p,p),'constant')

def F(S,H,W):
    # L,Uに頂点があって、RDに第3の頂点がある場合。
    # Rは数えずDだけ数えておく
    cnt = 0
    diag = np.zeros((H+p,W+p),np.int64)
    diag[:H,:W] += S[p:-p,p:-p]
    for n in range(1,H+p):
        diag[n,:W] += diag[n-1,1:W+1]
    for n in range(1,p):
        cnt += (S[1+p:H+1+p,1-n+p:W+1-n+p] * S[1-n+p:H+1-n+p,1+p:W+1+p] * (diag[1+n:H+1+n,1:W+1]-diag[1:H+1,1+n:W+1+n])).sum()
    return cnt

x = []
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))
S = S.T[::-1,:] # 90度回転
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))

answer = sum(x)
print(answer)
### BUGGY CODE ###

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

dp = [True] * THE_NUM

prev_num = -1
for i in A:
  # if the same number appears as before, that number cannot be counted in the answer.
  if prev_num == i:
    dp[i] = False
  prev_num = i
  for j in range(i * 2, THE_NUM, i):
    dp[j] = False

ans = 0
for i in A:
  # the same number after the second will not counted in the answer.
  if dp[i] == True:
    ans += 1

print(ans)


### FIXED CODE ###

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

dp = [True] * THE_NUM

prev_num = -1
for i in A:
  # if the same number appears as before, that number cannot be counted in the answer.
  if prev_num != i:
    for j in range(i * 2, THE_NUM, i):
      dp[j] = False
  else:
    dp[i] = False
  prev_num = i

ans = 0
for i in A:
  # the same number after the second will not counted in the answer.
  if dp[i] == True:
    ans += 1

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

import math
import itertools
X = int(input())

P = [x for x in range(1, X+1)]
Q = itertools.accumulate(P)
for i, q in enumerate(Q):
    if q>=X:
        print(i+1)
        break

### FIXED CODE ###

X = int(input())

for i in range(1, X+1):
    if i*(i+1)//2 >= X:
        print(i)
        break
### BUGGY CODE ###

import numpy as np

def main():
    N, A = map(int, input().split())
    X = tuple(map(int, input().split()))

    nx = max(A, max(X)) * N
    dp = np.array([[[0] * (nx + 1) for _ in [0] * (N + 1)] for _ in [0] * (N + 1)])

    for i in range(N + 1):
        for j in range(N + 1):
            for k in range(nx + 1):
                if j == 0 and k == 0:
                    dp[i][j][k] = 1
                elif i >= 1 and k < X[i-1]:
                    dp[i][j][k] = dp[i-1][j][k]
                elif i >= 1 and j >= 1 and k >= X[i-1]:
                    dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

    ans = 0
    for k in range(1, N + 1):
        ans += dp[N][k][k*A]
    print(ans)

main()


### FIXED CODE ###

def main():
    N, A = map(int, input().split())
    X = tuple(map(int, input().split()))

    x = [i - A for i in X]
    nx = max(X) * N
    dp = [[0] * (2 * nx + 1) for _ in [0] * (N + 1)]
    for i in range(N + 1):
        for j in range(2 * nx + 1):
            if not i:
                if j == nx:
                    dp[i][j] = 1
            elif j - x[i-1] < 0 or j - x[i-1] > 2 * nx:
                dp[i][j] = dp[i-1][j]
            elif 0 <= j - x[i-1] <= 2 * nx:
                dp[i][j] = dp[i-1][j] + dp[i-1][j - x[i-1]]
    print(dp[N][nx] - 1)

main()
### BUGGY CODE ###

n=int(input())
a=list(map(int, input("").split()))
o=0
for i in range(n-1):
    for j in range(i+1,n):
        o+=a[i]*a[j]
        o%=10**9+7
print(o)

### FIXED CODE ###

n=int(input())
a=list(map(int, input("").split()))
o=0
aa=[]
for i in a:
    aa.append(i**2)
s=sum(a)
o=(s**2-sum(aa))//2
o%=10**9+7
print(o)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    a.sort()
    maxa=a[len(a)-1]
    maxa = maxa // 2
    a[len(a)-1] = maxa
print(sum(a))

### FIXED CODE ###

import heapq

def int_minus(x):
    return -1 * int(x)

n,m=map(int,input().split())
a=list(map(int_minus,input().split()))
heapq.heapify(a)
for i in range(m):
    maxa=-1 * heapq.heappop(a)
    maxa = maxa // 2
    heapq.heappush(a, -1 * maxa)
print(-1 * sum(a))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
result = []

for i in range(N) :
  for j in range(int(N/2)+1) :
    if A[j] == i+1 :
      print(j+1, end="")
      print(" ", end="")
      break
    elif A[N-1-j] == i+1 :
      print(N-j, end="")
      print(" ", end="")
      break
  

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
result = [0 for i in range(N)]
  
for i in range(N) :
  result[A[i]-1] = i+1

for i in range(N) :
  print(result[i], end="")
  print(" ", end="")
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[0] * (W+2)]
    D += ([[0] + [float("inf")]*W + [0] for i in range(H)])
    D.append([0]*(W+2))
    G = [["#"]*(W+2)]
    G += [["#"]+[i for i in input().strip()]+["#"] for i in range(H)]
    G.append(["#"]*(W+2))
    for i in range(1, H+1):
        for j in range(1, W+1):
            if G[i][j] == "#":
                ls.append([i, j, 0])
                D[i][j] = 0

    while len(ls) > 0:
        h, w, depth = ls.popleft()
        if depth + 1 < D[h+1][w] and G[h+1][w] != "#":
            ls.append([h+1, w, depth+1])
            D[h+1][w] = depth + 1
        if depth + 1 < D[h-1][w] and G[h-1][w] != "#":
            ls.append([h-1, w, depth+1])
            D[h-1][w] = depth + 1
        if depth + 1 < D[h][w+1] and G[h][w+1] != "#":
            ls.append([h, w+1, depth+1])
            D[h][w+1] = depth + 1
        if depth + 1 < D[h][w-1] and G[h][w-1] != "#":
            ls.append([h, w-1, depth+1])
            D[h][w-1] = depth + 1

    ans = 0
    for h in range(1, H+1):
        ans = max(ans, max(D[h]))
        
    return ans
    
print(bfs())

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 1

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

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

N=int(input())
A=[int(x) for x in input().split()]
ans=1
for i in A:
    ans*=i
if ans>10**18:
    print(-1)

else:
    print(ans)

### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
A.sort(reverse=True)
result=1
if 0 in A:
    print(0)

else:
    for i in A:
        result*=i
        if result>10**18:
            print(-1)
            break
    else:
        print(result)
### BUGGY CODE ###

N = int(input())
L = [[int(x) for x in input().split()] for _ in range(N-1)]

dic = {}
dic_d = {}
visited = [0]*(N+1)
for i in range(N-1):
    if visited[L[i][0]] == 1:
        dic[L[i][0]].append(L[i][1])
        dic_d[L[i][0]].append(L[i][2])
    else:
        dic[L[i][0]] = [L[i][1]]
        dic_d[L[i][0]] = [L[i][2]]
        visited[L[i][0]] = 1
    if visited[L[i][1]] == 1:
        dic[L[i][1]].append(L[i][0])
        dic_d[L[i][1]].append(L[i][2])
    else:
        dic[L[i][1]] = [L[i][0]]
        dic_d[L[i][1]] = [L[i][2]]
        visited[L[i][1]] = 1

ans_list = ["0"]*(N+1)
q = [1]
D = [0]
visited = [0]*(N+1)
while len(q) > 0:
    v = q.pop(0)
    d = D.pop(0)
    for i in range(len(dic[v])):
        if visited[dic[v][i]] == 0:
            q.append(dic[v][i])
            D.append(d+dic_d[v][i])
            visited[dic[v][i]] = 1
            if (d+dic_d[v][i])%2 == 1:
                ans_list[dic[v][i]] = "1"
                
for i in range(1, N+1):
    print(ans_list[i])

### FIXED CODE ###

from collections import deque

N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    edge[u-1].append([v-1, w])
    edge[v-1].append([u-1, w])
    
d = [0]*(N)

q = deque()
q.append([0, 0])
visited = [0]*(N)
while q:
    temp = q.pop()
    for L in edge[temp[0]]:
        if visited[L[0]] == 0:
            d[L[0]] = L[1] + temp[1]
            q.append([L[0], d[L[0]]])
            visited[L[0]] = 1
            
for i in range(N):
    print(d[i]%2)
### BUGGY CODE ###

n=int(input())
ans = len(str(n))
l = [ i for i in range(1,n+1) if i*i <= n]
for a in l[::-1]:
    if n % a == 0:
        print( max(len(str(a)),len(str(int(n / a)))))
        break

### FIXED CODE ###

import math
n=int(input())
k = math.floor(math.sqrt(n))
for a in range(k+1,0,-1):
    if n % a == 0:
        print(max(len(str(a)),len(str(n//a))))
        break
### BUGGY CODE ###

#input
S = str(input())

#output
from collections import Counter
#2019 = 3 * 673
N = len(S)
#上からi桁目までの数を決めた時2019の個数をdp[i]とする。
dp = [0] * (N+1)
dp[1] = int(S[-1])
for i in range(1, N):
    dp[i+1] = (dp[i] + int(S[-(i+1)]) * 10**i) % 2019

T = Counter(dp[1:])

answer = 0
answer += T[0]

for t in T.values():
    if t >= 2:
        answer += t*(t-1)//2

print(answer)

### FIXED CODE ###

#input
S = str(input())[::-1]

#output
from collections import Counter
#2019 = 3 * 673
N = len(S)
#上からi桁目までの数を決めた時2019の個数をdp[i]とする。
dp = [0] * (N)
dp[0] = int(S[0])
times =10
for i in range(N-1):
    dp[i+1] = dp[i] + times * int(S[i+1])
    dp[i+1] %= 2019
    times *= 10
    times %= 2019

T = Counter(dp)

answer = T[0]

for t in T.values():
    answer += t*(t-1)//2

print(answer)
### BUGGY CODE ###

def main(n) : 
    i = 1
    final = []
    while i <= n : 
        if (n % i==0) : 
            final.append(i,)
        i = i + 1
    return len(final)
n = int(input())
ans = []
for i in range(1, n+1):
    ans.append(main(i))
val = 1
final_ans = 0
for i in ans:
    final_ans+=(val*i)
    val+=1
print(final_ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    ans += ((N // i) * ((N // i)+1) // 2) * i 
print(ans)
### BUGGY CODE ###

h, w, m = map(int, input().split())
lsh = [0] * h
lsw = [0] * w

bom = []
for _ in range(m):
    m1, m2 = map(int, input().split())
    lsh[m1 - 1] += 1
    lsw[m2 - 1] += 1
    bom.append((m1-1, m2-1))
#print(lsh)
#print(lsw)

lshmax = max(lsh)
lswmax = max(lsw)

jd= False

for i in range(h):
    if lsh[i] == lshmax:
        for j in range(w):
            if lsw[j] == lswmax:
                if (i, j) not in bom:
                    jd= True
                    #print(i,j)
if jd:
    print(lshmax+lswmax)
else:
    print(lshmax + lswmax -1)

### FIXED CODE ###

def main():
    h, w, m = map(int, input().split())
    lsh = [0] * h
    lsw = [0] * w

    bom = set()
    for _ in range(m):
        m1, m2 = map(int, input().split())
        lsh[m1 - 1] += 1
        lsw[m2 - 1] += 1
        bom.add((m1-1, m2-1))

    lshmax = max(lsh)
    lswmax = max(lsw)

    hin = [i for i in range(h) if lsh[i] == lshmax]
    win = [i for i in range(w) if lsw[i] == lswmax]

    for i in hin:
        for j in win:
            if (i, j) not in bom:
                print(lshmax + lswmax)
                exit(0)
    else:
        print(lshmax + lswmax -1)


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

n,m = map(int,input().split())
data = [tuple(map(int,input().split())) for i in range(n)]
data.sort(key = lambda tup:tup[0])
salary =[]
ans=0
prev=0
memo=0
for day in range(m):
	for i in range(memo,n):
		if data[memo][0]<=(day+1):
			salary.append(data[memo][1])
			memo+=1
		else:
			break
	ans+=max(salary ,default=0)
	if max(salary ,default=0) !=0:
		salary[salary.index(max(salary))]=0
print(ans)








### FIXED CODE ###

import heapq
n,m = map(int,input().split())
AB =[tuple(map(int,input().split())) for i in range(n)]
ans,memo=0,0
hq=[]
AB.sort(key=lambda tup:tup[0])
for day in range(m):
	for i in range(memo,n):
		if AB[i][0]<=(day+1):
			heapq.heappush(hq,-AB[i][1])
			memo+=1
		else:
			break
	if len(hq):	
		ans += -heapq.heappop(hq)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import *
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    def dfs(x):
        for e in edg[x]:
            heappush(d[x],dfs(e) + 1)
        tmp = 0
        while d[x]:
            t = heappop(d[x])
            tmp += 1
            if t > tmp:
                tmp = t
        return tmp
    n = II()
    edg = [[] for _ in range(n)]
    d = defaultdict(list)
    for i in range(n - 1):
        a = II() - 1
        edg[a].append(i + 1)
    print(dfs(0))
    return


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


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import *
from bisect import bisect_left, bisect_right
import sys
sys.setrecursionlimit(2147483647)
input = sys.stdin.readline
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10
input=lambda:sys.stdin.readline().rstrip()
#solve
def solve():

    n = int(input())
    edg = [[] for _ in range(n)]
    dp = [None] * n
    for i in range(1,n):
        u = int(input()) - 1
        edg[u].append(i)
        edg[i].append(u)

    def dfs(v,p=-1)->int:
        if (dp[v] is not None): return dp[v]
        if (edg[v] == [p]):
            dp[v] = 0
            return 0
        tmp = []
        for nv in edg[v]:
            if (nv == p): continue
            tmp.append(dfs(nv,v))
        dp[v] = max(1 + i + x for i, x in enumerate(sorted(tmp, reverse=1)))
        return dp[v]
    
    print(dfs(0))
    return


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

#<C>
import math
N = int(input())
for n in range(1, N + 1):
    ans = 0
    x = math.ceil(n ** (1/2))
    for i in range(1, x):
        for j in range(1, x):
            for k in range(1, x):
                if i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i == n:
                    ans += 1
    print(ans)


### FIXED CODE ###

N = int(input())
A = [0] * (N + 1)
for i in range(1, 102):
    for j in range(1, 102):
        for k in range(1, 102):
            t = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + i * k
            if t <= N:
                A[t] += 1
for n in range(1, N + 1):
    print(A[n])
### BUGGY CODE ###

# AtCoder Beginner Contest 177
# C - Sum of product of pairs

from itertools import combinations

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

mod=10**9+7

ans=0

for v in combinations(ls,2):
    ans+= (v[0]*v[1])%mod
    ans%=mod

print(ans)


### FIXED CODE ###

# AtCoder Beginner Contest 177
# C - Sum of product of pairs

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

mod=10**9+7

ans=0
accumls=[0]

for i in range (N):
    accumls.append(accumls[-1]+ls[i])

for i in range (N-1):
    ans+= ls[i]*(accumls[-1]-accumls[i+1])
    ans%=mod

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

# 1のnumpyバージョン
import numpy as np
def f():
    n = int(input())
    a = list(map(int, input().split()))
    x = list(sorted(set(a)))
    a = np.array(a, dtype="i8")
    Li = -1
    Ri = len(x) - 1
    while Li + 1 < Ri:
        i = (Li + Ri) // 2
        xi = x[i]
        s = 0
        lr = np.cumsum((a > xi) * 2 - 1, dtype="i8")
        M = np.sum((lr >= 0) * 2 - 1)
        for l in range(1, n):
            lr[l:] -= lr[l - 1]
            M += np.sum((lr[l:] >= 0) * 2 - 1)
        if M >= 0:
            Li = i
        else:
            Ri = i
    print(x[Ri])

f()

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])