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

class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
N=int(input())
A=[int(i) for i in input().split()]
if ((N*(N+1))//2)%2==1:
    a=((N*(N+1))//2)//2+1
else:
    a=((N*(N+1))//2)//2
#a=((N*(N+1))//2)-((N*(N+1))//2)//2-1
def f(s):#ans is ijou s
    X=[1 if a>=s else -1 for a in A]
    p=[0]*(N+1)
    ma=0
    mi=0
    for i in range(1,N+1):
        p[i]=p[i-1]+X[i-1]
        ma=max(p[i],ma)
        mi=min(p[i],mi)
    tree=BIT(ma-mi+1)
    num=0
    for i in range(1,N+2):
        num+=tree.search(p[i-1]-mi+1)
        tree.add(p[i-1]-mi+1,1)
    if num>=a:
        return True
    else:
        return False
x=10**9+1
y=-1
while x-y>1:
    mid=(x+y)//2
    if f(mid):
        y=mid
    else:
        x=mid
print(y)


### FIXED CODE ###

class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
N=int(input())
A=[int(i) for i in input().split()]
if ((N*(N+1))//2)%2==1:
    a=((N*(N+1))//2)//2+1
else:
    a=((N*(N+1))//2)//2
#a=((N*(N+1))//2)-((N*(N+1))//2)//2-1
def f(s):#ans is ijou s
    X=[1 if a>=s else -1 for a in A]
    p=[0]*(N+1)
    for i in range(1,N+1):
        p[i]=p[i-1]+X[i-1]
    tree=BIT(2*N+1)
    num=0
    for i in range(1,N+2):
        num+=tree.search(p[i-1]+N+1)
        tree.add(p[i-1]+N+1,1)
    if num>=a:
        return True
    else:
        return False
x=10**9+1
y=-1
while x-y>1:
    mid=(x+y)//2
    if f(mid):
        y=mid
    else:
        x=mid
print(y)
### BUGGY CODE ###

n=int(input())
s=input()
a=[0 for _ in range(n*(n-1)*(n-2)//6)]
ind=0
for i in range(n-2):
  p=s[i]
  #q
  for j in range(i+1,n-1):
    r=p
    r+=s[j]
    for k in range(j+1,n):
      t=r
      t+=s[k]
      a[ind]=t
      ind+=1
#print(a)
a=list(set(a))
#print(a)
print(len(a))


### FIXED CODE ###

n=int(input())
s=input()
list=["" for _ in range(1000)]
ans=0
for i in range(1000):
  t=str(i)
  u="0"*(3-len(t))+t
  j=0
  exi=0
  p=u[0]
  for x in s:
    if x==p:
      j+=1
      if j==3:
        ans+=1
        break
      p=u[j]
    

  









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

import sys
input = sys.stdin.readline

N = int(input())
l = [[int(input())]]

for i in range(N-1):
  ai = int(input())
  flag = False
  for m in l:
    if max(m) < ai:
      m.append(ai)
      flag = True
      break
  if flag == False:
    l.append([ai])
    
print(len(l))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_right

N = int(input())
l = [-int(input())]

for i in range(N-1):
  ai = -int(input())
# 各色の最大値がlの要素になるようにリストを拡大させていく
  if l[-1] <= ai:
    l.append(ai)
  else:
    b = bisect_right(l, ai)
    l[b] = ai
    
print(len(l))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
inf=998244353


N,K=map(int,input().split())
SS=[]

for i in range(K):
    s1,s2=map(int,input().split())
    for j in range(s1,s2+1):
        SS.append(j)



table = [0 for k in range(N-1)] 

for s in SS:
    if s<=N-1:
        table[s-1]+=1
for i in range(N-1):
    if table[i]!=0:
        for s in SS:
            if i+s<N-1:
                table[i+s]+=table[i]
                table[i+s]%=inf
                #print(table,i,s)
print(table[-1]%inf)

### FIXED CODE ###

inf=998244353


N,K=map(int,input().split())
SS=[list(map(int,input().split())) for i in range(K)]

SS.sort()

table = [0 for k in range(N)] 
diff = [0 for k in range(N-1)]

table[0]=1
diff[0]=-1

for i in range(N-1):
    if table[i]!=0:
        for s in SS:
            lef=s[0]
            rig=s[1]
            if i+lef-1<N-1:
                diff[i+lef-1]+=table[i]
            if i+rig<N-1:
                diff[i+rig]-=table[i]
    table[i+1]=table[i]+diff[i]
    table[i+1]%=inf

print(table[N-1])
### BUGGY CODE ###

n, m, d = map(int, input().split())

#print(2 * (n - d) * (m - 1) / (n ** m))
# print((n - d) * 2 * (n - 1) * (m - 1) * (n ** (m - 1)) / (n ** m))
if d != 0:
    print((n - d) * 2 * (m - 1) * (n ** (m - 2)) / (n ** m))
else:
    print((m - 1) / n)


### FIXED CODE ###

n, m, d = map(int, input().split())

#print(2 * (n - d) * (m - 1) / (n ** m))
# print((n - d) * 2 * (n - 1) * (m - 1) * (n ** (m - 1)) / (n ** m))
if d != 0:
    print((n - d) * 2 * (m - 1) / (n ** 2))
else:
    print((m - 1) / n)
### BUGGY CODE ###

H, W, M = map(int, input().split())
bombs = []
for i in range(H):
    bombs.append([False] * W)
rows = []
for i in range(H):
    rows.append([i, 0])
cols = []
for i in range(W):
    cols.append([i, 0])
for i in range(M):
    y, x = map(lambda x: x - 1, map(int, input().split()))
    bombs[y][x] = True
    rows[y][1] += 1
    cols[x][1] += 1


rows = sorted(rows, key=lambda x: x[1], reverse=True)
cols = sorted(cols, key=lambda x: x[1], reverse=True)
answer = 0
for row in rows:
    a = cols[0][1] + row[1] - (1 if bombs[row[0]][cols[0][0]] else 0)
    if a > answer:
        answer = a
for col in cols:
    a = rows[0][1] + col[1] - (1 if bombs[rows[0][0]][col[0]] else 0)
    if a > answer:
        answer = a
print(answer)

### FIXED CODE ###

H, W, M = map(int, input().split())
bombs = {}
rows = []
cols = []
for i in range(H):
    rows.append([i, 0])
for i in range(W):
    cols.append([i, 0])
for i in range(M):
    y, x = map(lambda x: x - 1, map(int, input().split()))
    bombs[(y,x)] = True
    rows[y][1] += 1
    cols[x][1] += 1


rows = sorted(rows, key=lambda x: x[1], reverse=True)
cols = sorted(cols, key=lambda x: x[1], reverse=True)
answer = 0
for row in rows:
    a = cols[0][1] + row[1] - (1 if (row[0], cols[0][0]) in bombs else 0)
    if a > answer:
        answer = a
for col in cols:
    a = rows[0][1] + col[1] - (1 if (rows[0][0], col[0]) in bombs else 0)
    if a > answer:
        answer = a
print(answer)
### BUGGY CODE ###

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

ans = 0
for i in range(2, N+1):
    for j in range(N-i+1):
        tmp = sorted(set(P[j:j+i]), reverse=True)[1]
        ans += tmp
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
 
index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index
 
left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]
ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    # print (i, index)
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    # print ('l1 =', l1, ' l2 =', l2, ' r1 =', r1, ' r2 =', r2)
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))
 
    left_next_Index[r1] = l1
    right_next_Index[l1] = r1
 
print (ans)
### BUGGY CODE ###

s=input()
a=input()
a=a.split()
c=1
for x in a:
  c=c*int(x)
if c > 10**18:
  print("-1")
else:  
  print(c) 


### FIXED CODE ###

a=int(input())
A=list(map(int,input().split()))
ans=1
if A.count(0)==0:
    for x in A:
      ans*=x
      if ans>10**18:
        break


    if ans>10**18:
      print(-1)
    else:
      print(ans)
else:
  print(0)
### BUGGY CODE ###

from collections import deque, defaultdict

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

# 現在末尾に追加される山より若い山で，最も個数の大きいものが次の山になる
# 他の山を次の山の個数以下まで減らす

nextNumIndex = deque([0])

for i, a in enumerate(A[1:], start=1):
    if a > A[nextNumIndex[-1]]:
        nextNumIndex.append(i)

ans = defaultdict(int)
while len(nextNumIndex) > 1:
    nowNum = nextNumIndex.pop()
    nextNum = nextNumIndex[-1]
    cnt = 0
    for i in range(nextNum, N):
        cnt += max(0, A[i] - A[nextNum])
        A[i] = min(A[i], A[nextNum])

    ans[nowNum] = cnt

ans[nextNumIndex.pop()] = sum(A)

out = []
for i in range(N):
    out.append(ans[i])
print(*out, sep='\n')

### FIXED CODE ###

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

# 現在末尾に追加される山より若い山で，最も個数の大きいものが次の山になる
# 他の山を次の山の個数以下まで減らす

ans = [0] * N

numList = [(a, i) for i, a in enumerate(A)]
numList.sort(reverse=True)
numList.append((0, 0))

y = float('inf')
for c, (a, i) in enumerate(numList[: N], start=1):
    y = min(y, i)
    ans[y] += c * (a - numList[c][0])

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

n, m = map(int, input().split())
a = list(map(int, input().split()))
nedan_list = []
for i in range(n):
  price = a[i]
  nedan_list.append((i, price))
  while price > 0:
    price //= 2
    nedan_list.append((i, price))

nedan_list = sorted(nedan_list, key=lambda x:x[1], reverse=True)
count = 0
saisyo_list = [True]*n
for e in nedan_list[m:]:
  if saisyo_list[e[0]]:
    saisyo_list[e[0]] = False
    count += e[1]
print(count)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a) 

for i in range(m):
  max_ = -heapq.heappop(a)
  d = max_ // 2
  heapq.heappush(a, -d)

c = 0
for i in range(len(a)):
  c -= heapq.heappop(a)
print(c)
### BUGGY CODE ###

N=int(input())
a=[]
for i in range(N):
  a.append(input())
b=list(set(a))
c=[]
for j in range(len(b)):
  c.append(a.count(b[j]))
d=int(c.count(max(c)))
e=[]
for k in range(d):
  e.append(b[c.index(max(c))])
  c[c.index(max(c))]=0
for l in range(len(e)):
  print(min(e))
  e.remove(min(e))

### FIXED CODE ###

N=int(input())
a=[]
for i in range(N):
  a.append(input())
b={}
for j in range(len(a)):
  if a[j] in b:
    b[a[j]]+=1
  else:
    b[a[j]]=1
max_b=max(b.values())
c=[]
for k,l in b.items():
  if l==max_b:
    c.append(k)
c.sort()
for m in c:
  print(m)
### BUGGY CODE ###

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

R=0

for i in range(Q):
    temp=list(input().split())
    if int(temp[0])==1:
        R+=1
    elif int(temp[0])==2:
        F=int(temp[1])
        c=temp[2]
        if F==1:
            if R%2==0:
                S=c+S
            else:
                S=S+c
        elif F==2:
            if R%2==0:
                S=S+c
            else:
                S=c+S

if R%2==1:
    ans=S[-1::-1]
    print(ans)
else:
    print(S)



### FIXED CODE ###

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

R=0
S1=""
S2=""
for i in range(Q):
    temp=list(input().split())

    if int(temp[0])==1:
        S=S1+S+S2
        S1=""
        S2=""
        R+=1
    elif int(temp[0])==2:
        F=int(temp[1])
        c=temp[2]
        if F==1:
            if R%2==0:
                S1=c+S1
            else:
                S2=S2+c
        elif F==2:
            if R%2==0:
                S2=S2+c
            else:
                S1=c+S1
S=S1+S+S2

if R%2==1:
    ans=S[-1::-1]
    print(ans)
else:
    print(S)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
res = []
for i in range(N):
    if i%2 == 1:
        res.insert(0,L[i])
    else:
        res.append(L[i])

if N%2 == 1:
    res.reverse()
for i in range(N):
    print(str(res[i]) + ' ', end="")

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.reverse()
lim = int(N/2)
if N%2 == 0:
    for i in range(lim):
        print(str(L[2*i]) + ' ', end="")

    L.reverse()
    for i in range(int(N/2)):
        print(str(L[2*i]) + ' ', end="")
else:
    lim += 1
    for i in range(lim):
        print(str(L[2*i]) + ' ', end="")

    L.reverse()
    for i in range(int(N/2)):
        print(str(L[2*i+1]) + ' ', end="")
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A = [input() for _ in range(H)]

D = [[0] * W for _ in range(H)]

Q = deque()
Q1 = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            D[i][j] = 1
            Q.append([i, j])

yudlr = [1, -1, 0, 0]
xudlr = [0, 0, -1, 1]

C = 0
while len(Q) > 0:
    C += 1
    while len(Q) > 0:
        Q1.append(Q.pop())
    while len(Q1) > 0:
        q = Q1.popleft()
        y = q[0]
        x = q[1]
        for i in range(4):
            y1 = y + yudlr[i]
            x1 = x + xudlr[i]
            if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
                continue
            if D[y1][x1] == 1:
                continue
            D[y1][x1] = 1
            Q.append([y1, x1])

print(C - 1)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
Q = deque()
h = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            Q.append([i, j])
        else:
            h += 1
Qtmp = deque()

yudrl = [0, 1, 0, -1]
xudrl = [1, 0, -1, 0]

c = 0
while h > 0:
    c += 1
    while len(Q) > 0:
        Qtmp.append(Q.pop())
    while len(Qtmp) > 0:
        q = Qtmp.pop()

        for i in range(4):
            y = q[0] + yudrl[i]
            x = q[1] + xudrl[i]

            if y < 0 or y > H - 1 or x < 0 or x > W - 1:
                continue
            if A[y][x] == '#':
                continue
            A[y][x] = '#'
            h -= 1
            Q.append([y, x])
print(c)
### BUGGY CODE ###

V, E = map(int, raw_input().split())
g = [[] for i in xrange(V)]
cost = {}
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    g[s].append((t, d))
    cost[s,t] = d
get = cost.get
INF = 10**9
ALL = 2**V-1
dp = [[-1]*V for i in xrange(2**V)]
def dfs(state, v, s):
    if dp[state][v] != -1:
        return dp[state][v]
    if state == ALL:
        res = get((v, s), INF)
        dp[state][v] = res
        return res
    res = INF
    for t, d in g[v]:
        if not state & (1 << t):
            res = min(res, dfs(state | (1 << t), t, s) + d)
    dp[state][v] = res
    return res
def solve(v):
    global dp
    dp = [[-1]*V for i in xrange(2**V)]
    return dfs(1<<v, v, v)
res = min(solve(v) for v in xrange(V))
print res if res<INF else -1

### FIXED CODE ###

import sys
readline = sys.stdin.readline
V, E = map(int, readline().split())
g = [[] for i in xrange(V)]
cost = {}
to = [0]*V
for i in xrange(E):
    s, t, d = map(int, readline().split())
    g[s].append((t, d))
    cost[s,t] = d
    to[s] |= 1 << t
get = cost.get
INF = 10**9
ALL = 2**V-1
dp = {}
start = 0
def dfs(state, v):
    key = (state, v)
    if key in dp: return dp[key]
    if state == ALL:
        dp[key] = res = get((v, start), INF)
        return res
    dp[key] = res = min((dfs(state | (1 << t), t) + d for t, d in g[v] if not state & (1 << t))) if state & to[v] != to[v] else INF
    return res
res = dfs(1, 0)
print res if res<INF else -1
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
P=10**9+7
count=[0]*60    #マジックナンバー

def culc(a):
    global count

    i=0
    while a>0:
        if a&1==1:
            count[i]+=1
        a=a>>1
        i+=1

def res():
    global N
    global count

    res=0
    for i in range(len(count)):
        res=(res+(2**i)*count[i]*(N-count[i]))%P

    return res

for index in range(N):
    culc(A[index])

ans=res()
print(ans)



### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
P=10**9+7
count=[0]*60    #マジックナンバー

def culc(a):
    global count

    i=0
    while a>0:
        if a&1==1:
            count[i]+=1
        a=a>>1
        i+=1

def res():
    global N
    global count

    res=0
    for i in range(len(count)):
        res=(res+(2**i)*count[i]*(N-count[i]))%P

    return res

for index in range(N):
    culc(A[index])

ans=res()
print(ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
assert len(A) == N
assert len(B) == M
# K分以内に読む数の最大化

cumA = []
cumB = []
sumA = 0
sumB = 0
for a in A:
  sumA += a
  cumA.append(sumA)
for b in B:
  sumB += b
  cumB.append(sumB)

maximum = 0
for n in range(1, K+1, 1):
  timeA = n
  timeB = K - n
  maxA = [i for i,a in enumerate(cumA) if a <= timeA]
  maxB = [i for i,b in enumerate(cumB) if b <= timeB]
  maxA = max(maxA) + 1 if len(maxA) else 0
  maxB = max(maxB) + 1 if len(maxB) else 0
  maximum = max(maximum, maxA + maxB)
print(maximum)

### FIXED CODE ###

N , M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a,b=[0],[0]
for i in range(N): a.append(a[i] + A[i])
for i in range(M): b.append(b[i] + B[i])
ans,j=0,M
for i in range(N+1):
  if a[i]>K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

import bisect
n = int(input())
l = sorted(list(map(int, input().split())))

dic = {}
ans = 0
for i in range(n-1):
  for j in range(i+1, n):
    tmp = l[i] + l[j]
    
    if tmp in dic.keys():
      index2 = dic[tmp]
    else:
      index2 = bisect.bisect_left(l, tmp)
      dic[tmp] = index2
      
    if l[j] in dic.keys():
      index1 = dic[l[j]]
    else:
      index1 = bisect.bisect_left(l, l[j])
      dic[l[j]] = index1
      
    
    if l[i] == l[j]:
      d = index2 - index1 - 2
    else:
      d = index2 - index1 - 1
    
    ans += max(d,0)
    
print(ans)

### FIXED CODE ###

import bisect as bs
n = int(input())
l = sorted(list(map(int,input().split())))

count = 0
for i in range(n):
  for j in range(i+1,n):
    index = bs.bisect_left(l,l[i]+l[j])
    count += index - j - 1
    
print(count)
### BUGGY CODE ###

N,M,K = map(int,input().split())
m = 998244353
ans = (M*pow(M-1,N-1,m))%m
alpha = 1
for k in range(1,K+1):
    alpha = alpha*(N-k)//(k)
    ans = (ans + M*alpha*pow(M-1,N-k-1,m))%m
print(ans)


### FIXED CODE ###

N,M,K = map(int,input().split())
m = 998244353
ans = (M*pow(M-1,N-1,m))%m
alpha = 1
for k in range(1,K+1):
    alpha = (alpha*(N-k)*pow(k,m-2,m))%m
    ans = (ans + M*alpha*pow(M-1,N-k-1,m))%m
print(ans)
### BUGGY CODE ###

def is_prime(num:int):
    if num == 1:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    r_num = int(num ** 0.5)
    for i in range(3, r_num + 1, 2):
        if num % i == 0:
            return False
    return True


def main():
    n = int(input())

    if n == 1:
        print(0)
        return

    cnt = 0
    r_n = int(n ** 0.5)
    for i in range(2, n):
        if n < i:
            break
        elif cnt == 0 and r_n+1 < i:
            break
        if n % i == 0 and is_prime(i):
            n = int(n/i)
            cnt += 1
            x = 2
            while True:
                q = i ** x
                if q > n:
                    break

                if n % q == 0:
                    n = int(n/q)
                    x += 1
                    cnt += 1
                else:
                    break

    if cnt == 0:
        cnt = 1
    print(cnt)


main()


### FIXED CODE ###

def is_prime(num:int):
    if num == 1:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    r_num = int(num ** 0.5)
    for i in range(3, r_num + 1, 2):
        if num % i == 0:
            return False
    return True


def main():
    n = int(input())

    if n == 1:
        print(0)
        return

    cnt = 0
    r_n = int(n ** 0.5)
    divided = []
    for i in range(2, n):
        if n < i:
            break
        elif cnt == 0 and r_n+1 < i:
            break
        if n % i == 0 and is_prime(i):
            n = int(n/i)
            divided.append(i)
            cnt += 1
            x = 2
            while True:
                q = i ** x
                if q > n:
                    break

                if n % q == 0:
                    n = int(n/q)
                    x += 1
                    cnt += 1
                else:
                    break
            if is_prime(n) and n not in divided:
                n = 1
                cnt += 1
                break

    if cnt == 0:
        cnt = 1
    print(cnt)


main()
### BUGGY CODE ###

import sys
import bisect
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

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



def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [A[t]]
    while prev[t] != s:
        path.append(A[prev[t]])
        prev[t] = prev[prev[t]]
    path.append(A[s])
    path = path[::-1]
    return path

def main():
    cost = [[float("inf") for i in range(N)] for i in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        cost[u][v] = 1
        cost[v][u] = 1

    for i in range(N):
        seq = dijkstra_back(0,i,N,N-1,cost)
        LIS = [seq[0]]
        for i in range(len(seq)):
            if seq[i] > LIS[-1]:
                LIS.append(seq[i])
            else:
                LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
        
        print(len(LIS))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

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

n = int(input())

for i in range(1, 1000000000):
  if i%2==0 and i%n==0:
    print(i)
    break
    

### FIXED CODE ###

n = int(input())

if n % 2 == 0:
  print(n)
else:
  print(2*n)
### BUGGY CODE ###

N=input()
S=[ list(raw_input()) for i in range(N)]

A=0
ans=0
for B in range(N):
	T=[ ["" for j in range(N)] for i in range(N)]

	for i in range(N):
		for j in range(N):
			T[i][j]=S[(i+A)%N][(j+B)%N]

	flag=0
	for i in range(N):
		if flag==-1: break
		for j in range(N):
			if T[i][j]==T[j][i]:
				pass
			else:
				flag=-1
				break
	else:
		ans+=1*N


print ans


### FIXED CODE ###

N=input()
S=[ list(raw_input()) for i in range(N)]

A=0
ans=0
for B in range(N):
	flag=0
	for i in range(N):
		if flag==-1: break
		for j in range(N):
			x1=(N+i-A)%N
			y1=(N+j-B)%N

			x2=(N+j-A)%N
			y2=(N+i-B)%N

			#print i,j,x1,y1,x2,y2
			if S[x1][y1]==S[x2][y2]:
				pass
			else:
				flag=-1
				#break
	else:
		ans+=1*N


print ans
### BUGGY CODE ###

n = int(input())
x = list(map(int,input().split()))
import numpy as np
import copy
np.median(x)
for i in range(n):
    x_c = copy.copy(x)
    x_c.pop(i)
    print("{}".format(int(np.median(x_c))))


### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
import numpy as np
import copy
md = np.median(x)
x_c = copy.copy(x)
x_c.sort()
a = x_c[int(n/2 - 1)]
b = x_c[int(n/2)]
for i in range(n):
    if x[i] < md:
        print(b)
    else:
        print(a)