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

import bisect

INF = 10 ** 10

N = int(input())
As = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(N-1)]

dfs_stack = [1]
ans = [-1] * N
lis = [INF] * (N+1)
rewinder = []

while dfs_stack:
    pos = dfs_stack.pop()
    for u, v in edges:
        if u == pos:
            if ans[v-1] == -1:
                dfs_stack.append(v)
            else:
                parent = v
        elif v == pos:
            if ans[u-1] == -1:
                dfs_stack.append(u)
            else:
                parent = u
    
    while rewinder:
        i, before, after = rewinder.pop()
        if after == As[parent-1]:
            rewinder.append( (i, before, after) )
            break
        else:
            lis[i] = before

    index = bisect.bisect_left(lis, As[pos-1])
    rewinder.append( (index, lis[index], As[pos-1]) )
    lis[index] = As[pos-1]
    ans[pos-1] = lis.index(INF)

print(*ans, sep = '\n')

### FIXED CODE ###

from bisect import bisect_left

INF = 10 ** 9

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

adj = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    adj[u-1].append(v-1)
    adj[v-1].append(u-1)

ans = [0] * N
LIS = [INF] * (N+1)
rewinder = []

parent = [-1] * N
stack = [0]
while stack:
    node = stack.pop()
    for next_node in adj[node]:
        if ans[next_node] == 0:
            parent[next_node] = node
            stack.append(next_node)

    while rewinder and rewinder[-1][0] != parent[node]:
        _, index, prev_value = rewinder.pop()
        LIS[index] = prev_value
    
    index = bisect_left(LIS, As[node])
    rewinder.append((node, index, LIS[index]))
    LIS[index] = As[node]

    ans[node] = bisect_left(LIS, INF)

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

from sys import setrecursionlimit
from collections import Counter
setrecursionlimit(1000000)
def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]

def find_components(n, connectors):
    nodes = [i for i in range(n)]
    for a, b in connectors:
        for e in range(n):
            if nodes[e] == nodes[a-1]: nodes[e] = nodes[b-1]
    return len(Counter(nodes))

n, m = m_in(int)
ab = [list(m_in(int)) for _ in range(m)]

ans = find_components(n, ab) - 1

print(ans)


### FIXED CODE ###

from sys import setrecursionlimit
from collections import Counter
import networkx as nx
setrecursionlimit(1000000)
def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]

def find_components(n, connectors):
    g = nx.Graph()
    for i in range(n): g.add_node(i+1)
    g.add_edges_from(connectors)
    return len(list(nx.connected_components(g)))


n, m = m_in(int)
ab = [list(m_in(int)) for _ in range(m)]

ans = find_components(n, ab) - 1

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

def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
    print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

    # 入力を整数に変換して受け取る
    def input_int():
        return int(input())

    def map_int_input():
        return map(int, input())

    MII = map_int_input

    def MII_split():
        return map(int, input().split())

    def MII_to_index():
        return map(to_index, input())

    def MII_split_to_index():
        return map(to_index, input().split())

    # 入力全てを整数に変換したものの配列を受け取る
    def list_int_inputs():
        return list(map(int, input()))

    LII = list_int_inputs

    def LII_split():
        return list(map(int, input().split()))

    # 2次元リスト化
    def LII_2D(rows_number):
        return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number):
        return [LII_split() for _ in range(rows_number)]

    N = input_int()
    As = LII_split()

    import numpy as np
    left = np.array(list(reversed(As)))
    right_list = []
    for i in range(len(As)):
        temp = As[:len(As)-i-1]
        for _ in range(i+1):
            temp.append(0)
        right_list.append(temp)
    # print(right_list)
    right = np.array(right_list).reshape(N, N)

    # print(right)
    # print(left)

    s = sum(np.matmul(left, right))
    print(s % (10 ** 9 + 7))
    # for i in range(N):
    #     for j in range(i + 1, N):
    #         s += As[j] * As[i]
    #         if s > 10 ** 9 + 7:
    #             s %= 10 ** 9 + 7
    # print(s)
resolve()

### FIXED CODE ###

def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
    print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

    # 入力を整数に変換して受け取る
    def input_int():
        return int(input())

    def map_int_input():
        return map(int, input())

    MII = map_int_input

    def MII_split():
        return map(int, input().split())

    def MII_to_index():
        return map(to_index, input())

    def MII_split_to_index():
        return map(to_index, input().split())

    # 入力全てを整数に変換したものの配列を受け取る
    def list_int_inputs():
        return list(map(int, input()))

    LII = list_int_inputs

    def LII_split():
        return list(map(int, input().split()))

    # 2次元リスト化
    def LII_2D(rows_number):
        return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number):
        return [LII_split() for _ in range(rows_number)]

    N = input_int()
    A = LII_split()

    s = 0
    right_sum = 0
    for i in reversed(range(N - 1)):
        right_sum += A[i + 1]
        s += A[i] * right_sum

        # 2乗は死ぬので累積和を使う（使えることは式を書き出せばわかる）
        # for j in range(i + 1, N):
        #     s += As[j] * As[i]
        if s > 10 ** 9 + 7:
            s %= 10 ** 9 + 7

    print(s)
    
resolve()
### BUGGY CODE ###

from collections import deque, defaultdict


def bfs(graph, start, ans_list):

    queue = deque([start])
    visited = set()
    distance = defaultdict(int)
    distance[start] = 0
    while queue:
        current_vertex = queue.popleft()
        visited.add(current_vertex)
        for v in graph[current_vertex]:
            if v not in visited and v not in queue:
                queue.append(v)
                ans_list[v] = current_vertex
    return ans_list

N, M = map(int, input().split())
paths = [tuple(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
for A, B in paths:
    graph[A].add(B)
    graph[B].add(A)

ans_list = {}
for i in range(2, N+1):
    ans_list[i] = 0

ans_list = bfs(graph, 1, ans_list)

print('Yes')
for x in ans_list.values():
    print(x)


### FIXED CODE ###

from collections import deque, defaultdict


def bfs(graph, start):

    queue = deque([start])
    visited = set()
    visited.add(start)
    parent = defaultdict(int)
    parent[start] = 0
    while queue:
        current_vertex = queue.popleft()
        for v in graph[current_vertex]:
            if v not in visited:
                queue.append(v)
                visited.add(v)
                parent[v] = current_vertex
    return parent

N, M = map(int, input().split())
paths = [tuple(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
for A, B in paths:
    graph[A].add(B)
    graph[B].add(A)

parent = bfs(graph, 1)

print('Yes')
for k, v in sorted(parent.items()):
    if v != 0:
        print(v)
### BUGGY CODE ###

def main():
    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))

    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()

### 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 = int(input())
H = list(map(int, input().split()))
 
count = 0
flg = True
tmp = H
 
for i in range(N):
  if H[i] != min(tmp):
    H[i] -= 1
  if i!=0 and H[i-1] > H[i]:
    flg = False
    break
  tmp = H[i:]

if flg==True:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
 
hmax = H[-1]
 
for h in reversed(H):
  if h <= hmax:
    hmax = h
    continue
  if h-1 <= hmax:
    hmax = h-1
    continue
  print('No')
  quit()

print('Yes')
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
c = 0
i = 0
for i in range(N):
  if c < N:
    b = A.count(i + 1)
    print(b)
    c += b
  else:
    print(o)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
L = [0] * n
for i in A:
    L[i - 1] += 1
for j in L:
    print(j)
### BUGGY CODE ###

s = input()
K = int(input())
subs = set()
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        subs.add(s[i:j])
arr = list(subs)
arr.sort()
print(arr[K-1])


### FIXED CODE ###

from heapq import nsmallest

s = input()
K = int(input())
subs = set()
for i in range(len(s)):
    for j in range(i + 1, min(i + 6, len(s) + 1)):
        subs.add(s[i:j])
arr = list(subs)
print(nsmallest(K, arr)[-1])
### BUGGY CODE ###

import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
S = int(input())
count = 0
l = [0]*2019

for i in range(1,len(str(S))+1):
   l[(S%10**i)%2019] += 1

count += l[0]
for j in range(1,len(l)):
    if l[j] >= 2:
        count += comb(l[j],2)

print(count)


### FIXED CODE ###

S = input()
count = 0
l = [0]*2019
l[0] = 1
mod = 2019
tmp = 0

for i in range(1,len(S)+1):
    tmp = (tmp + int(S[len(S)-i])*pow(10,i-1,mod))%mod
    l[tmp] += 1
    

for j in range(2019):
    if l[j] >= 2:
        count += l[j]*(l[j]-1)//2

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

n = int(input())
s = list(input())

import collections
c = collections.Counter(s)

ans = c["R"] * c["B"] * c["G"]

for i in range(n-2):
    for j in range(i+1,n-1):
        x = s[i]
        y = s[j]
        
        if x != y:
            if "R" not in [x,y]:
                if 2*j-i < n:
                    if s[2*j-i] == "R":
                        ans -= 1
                    
            elif "G" not in [x,y]:
                if 2*j-i < n:
                    if s[2*j-i] == "G":
                        ans -= 1
                    
            else:
                if 2*j-i < n:
                    if s[2*j-i] == "B":
                        ans -= 1
    
print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
ans = 0

R = [0] * n
G = [0] * n
B = [0] * n

r = 0
g = 0
b = 0

for i in range(n):
    if s[i] == "R":
        r += 1
        R[i] = r
    elif s[i] == "G":
        g += 1
        G[i] = g
    else:
        b += 1
        B[i] = b

for i in range(n-2):
    for j in range(i+1,n-1):
        x = s[i]
        y = s[j]
        
        if x != y:
            if "R" not in [x,y]:
                ans += R[n-1] - R[j]
                
                if 2*j-i < n:
                    if s[2*j-i] == "R":
                        ans -= 1
                    
            if "G" not in [x,y]:
                ans += G[n-1] - G[j]
                
                if 2*j-i < n:
                    if s[2*j-i] == "G":
                        ans -= 1
                    
            if "B" not in [x,y]:
                ans += B[n-1] - B[j]
                
                if 2*j-i < n:
                    if s[2*j-i] == "B":
                        ans -= 1
    
print(ans)
### BUGGY CODE ###

import math

N, M = map(int, input().split())
item_list = list(map(int, input().split()))

# 割引は出来るだけする
for i in range(M):
	item_list[item_list.index(max(item_list))] = math.floor(max(item_list) / 2)

print(sum(item_list))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
item_list = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(item_list)

# 割引は出来るだけする
for i in range(M):
	temp_min = heapq.heappop(item_list)
	heapq.heappush(item_list, (-1)*(-temp_min//2))
print(-sum(item_list))
### BUGGY CODE ###

n = int(input())
p = list(map(float, input().split()))
dp = [[0 for _ in range(n+1)] for _ in range(n)]
#dp[i][j]: iまで投げてj枚表の確率
dp[0][0] = 1 - p[0]
dp[0][1] = p[0]

for i in range(1, n):
	for j in range(i+2):
		if j == 0:
			dp[i][j] = dp[i-1][j] * (1 - p[i])
		else:
			dp[i][j] = dp[i-1][j] * (1 - p[i]) + dp[i-1][j-1] * p[i]

#print(dp)
ans = 0
for i in range(n//2 + 1, n+1):
	ans += dp[-1][i]
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(float, input().split()))
dp = [[0 for _ in range(n+1)] for _ in range(n)]
#dp[i][j]: iまで投げてj枚表の確率
dp[0][0] = 1 - p[0]
dp[0][1] = p[0]

for i in range(1, n):
	for j in range(i+2):
		if j == 0:
			dp[i][j] = dp[i-1][j] * (1 - p[i])
		else:
			dp[i][j] = dp[i-1][j] * (1 - p[i]) + dp[i-1][j-1] * p[i]

#print(dp)
ans = 0
for i in range(n//2 + 1, n+1):
	ans += dp[-1][i]
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
c = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            continue
        for k in range(j + 1, n):
            if s[i] == s[j] or s[i] == s[k] or s[j] == s[k]:
                continue
            if j - i == k - j:
                continue
            c += 1
print(c)

### FIXED CODE ###

n = int(input())
s = []
r, g, b = [0] * 3
for c in input():
    if c == 'R':
        s.append(0)
        r += 1
    elif c == 'G':
        s.append(1)
        g += 1
    else:
        s.append(2)
        b += 1

c = r * g * b
for i in range(n):
    for j in range(i + 1, n):
        k = j + (j - i)
        if k < n and s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            c -= 1

print(c)
### BUGGY CODE ###

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

ns = list()
c = 0

for i in range(K-1, N):
    tmp = 1
    for j in range(i-K+1, i+1):
        tmp *= scores[j]
    ns.append(tmp)
    if c >= 1 and ns[c-1] < ns[c]:
        print('Yes')
    elif c >= 1 and ns[c-1] >= ns[c]:
        print('No')
    c += 1
    

### FIXED CODE ###

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

for i in range(K, N):
    if scores[i] > scores[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())
S = tuple(input())
ans = 0
for i in range(1000):
  if i<10:
    cnt0= 0
    cnt1 = 0
    for j in range(N):
      if 2<=cnt0 and S[j]=="%d"%i:
        ans+=1
        break
      if S[j]=="0":
        cnt0+=1
        continue
  elif 10<=i<=99:
    cnt0=0
    cnt1=0
    cnt2=0
    i = list(str(i))
    for j in range(N):
      if 1<=cnt0 and 1<=cnt1 and S[j]=="%s"%i[1]:
        ans+=1
        break
      if S[j]=="0" and cnt0!=1:
        cnt0+=1
        continue
      if 1<=cnt0 and S[j]=="%s"%i[0]:
        cnt1 +=1
        continue
  elif 100<=i:
    cnt0=0
    cnt1=0
    cnt2=0
    i = list(str(i))
    for j in range(N):
      if 1<=cnt0 and 1<=cnt1 and S[j]=="%s"%i[2]:
        ans+=1
        #print(i)
        break
      if S[j]=="%s"%i[0] and cnt0!=1:
        cnt0+=1
        continue
      if 1<=cnt0 and S[j]=="%s"%i[1]:
        cnt1 +=1
        continue
print(ans)
      
      
      


### FIXED CODE ###

def main():
  N = int(input())
  S = tuple(input())
  ans = 0
  for i in range(1000):
    if i<10:
      cnt0= 0
      cnt1 = 0
      for j in range(N):
        if 2<=cnt0 and S[j]=="%d"%i:
          ans+=1
          break
        if S[j]=="0":
          cnt0+=1
          continue
    elif 10<=i<=99:
      cnt0=0
      cnt1=0
      cnt2=0
      i = list(str(i))
      for j in range(N):
        if 1<=cnt0 and 1<=cnt1 and S[j]=="%s"%i[1]:
          ans+=1
          break
        if S[j]=="0" and cnt0!=1:
          cnt0+=1
          continue
        if 1<=cnt0 and S[j]=="%s"%i[0]:
          cnt1 +=1
          continue
    elif 100<=i:
      cnt0=0
      cnt1=0
      cnt2=0
      i = list(str(i))
      for j in range(N):
        if 1<=cnt0 and 1<=cnt1 and S[j]=="%s"%i[2]:
          ans+=1
          #print(i)
          break
        if S[j]=="%s"%i[0] and cnt0!=1:
          cnt0+=1
          continue
        if 1<=cnt0 and S[j]=="%s"%i[1]:
          cnt1 +=1
          continue
  print(ans)
main()
### BUGGY CODE ###

N,M=map(int,input().split())
dp=[0]*(N)
for _ in range(M):
    L,R=map(int,input().split())
    for j in range(L-1,R):
        dp[j]+=1
print(dp.count(M))

### FIXED CODE ###

N,M=map(int,input().split())
l=0
r=float("Inf")
for i in range(M):
    L,R=map(int,input().split())
    l=max(l,L)
    r=min(r,R)
print(max(r-l+1,0))
### BUGGY CODE ###

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

J = []
J = [0] * N
for i in range(N):
    J[i] = sum(range(1, P[i] + 1)) / P[i]

A = []
A = [0] * N
for i in range(N):
    A[i] += sum(J[i: i + K])

print(max(A))

### FIXED CODE ###

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

#logging.debug("デバッグスタート") #
l = [[] for i in range(n)]#期待値
m = [[] for i in range(n - k + 1)]  #k個の合計

for i in range(n):
    l[i] = (1 + p[i]) / 2

#logging.debug("l = {}".format(l))#
m[0] = sum(l[0:k])
ans = m[0]

for i in range(1, n - k + 1):
    #logging.debug("m[i-1] = {} ,l[i-1] = {} ,l[i+k] = {}".format(m[i - 1], l[i - 1], l[i + k - 1]))  #
    m[i] = m[i - 1] - l[i - 1] + l[i + k - 1]
    if m[i] > ans:
        ans = m[i]

#logging.debug(m)#
print(ans)
### BUGGY CODE ###

from bisect import bisect_left as bl
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    if K > max(A):
        print("IMPOSSIBLE")
        exit()
    if K in A:
        print("POSSIBLE")
        exit()
    M = max(A)
    E = list(map(lambda x:abs(x-K),A))
    E = set(E)
    C = [A[i+1]-A[i] for i in range(N-1)]
    C = set(C)
    D = set(A)
    if E&D:
        print("POSSIBLE")
        exit()
    for i in range(2,int(M**0.5)+10):
        B = set(map(lambda x:x%i,A))
        if len(B) == 1:
            print("IMPOSSIBLE")
            exit()
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    if K > max(A):
        print("IMPOSSIBLE")
        exit()
    if K in A:
        print("POSSIBLE")
        exit()

    E = list(map(lambda x:abs(x-K),A))
    E = set(E)
    C = [A[i+1]-A[i] for i in range(N-1)]
    C = set(C)
    D = set(A)
    if E&D:
        print("POSSIBLE")
        exit()

    print("IMPOSSIBLE")
    

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

#!/usr/bin/env python3
import sys
 
 
def solve(N: int, X: int, Y: int):
    cst = [0 for _ in range(N)]
    nodes = [Node(i, N, X, Y) for i in range(N)]
    for i in range(N):
        for n in nodes:
            n.done = False
            n.cost = -1
        # nodes = []
        # for j in range(N):
        #     nodes.append(Node(j, N, X, Y))
        # nodes = [Node(i, N, X, Y) for i in range(N)]
        nodes[i].cost = 0
        while True:
            doneNode = Node(N, N, X, Y)
            for n in nodes:
                if n.done or n.cost < 0:
                    pass
                elif doneNode.num == N or n.cost < doneNode.cost:
                    doneNode = n
            if doneNode.num == N:
                break
            
            doneNode.done = True
            for i in doneNode.edges:
                if nodes[i].cost < 0 or doneNode.cost + 1 < nodes[i].cost:
                    nodes[i].cost = doneNode.cost + 1
        
        for n in nodes:
            cst[n.cost] += 1
    
    for i in range(1, len(cst)):
        print(int(cst[i] / 2))
        
 
 
 
class Node:
    def __init__(self, i, N, X, Y):
        self.num = i
        self.edges = set()
        if i == 0:
            self.edges.add(i+1)
        elif i == N - 1:
            self.edges.add(i-1)
        else:
            self.edges.add(i+1)
            self.edges.add(i-1)
        if i == X - 1:
            self.edges.add(Y - 1)
        elif i == Y - 1:
            self.edges.add(X - 1)
        self.done = False
        self.cost = -1
 
            
            
 
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(N, X, Y)
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
# from functools import total_ordering
import heapq

from collections import Counter as cl

def solve(N: int, X: int, Y: int):

    def dis(a,b):
        fw = abs(a-b)
        bw1 = abs(X-a)+abs(Y-b)+1
        bw2 = abs(X-b)+abs(Y-a)+1
        bw = min(bw1,bw2)
        return min(fw, bw)
    
    dist_l = [0]*(N-1)
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            dist_l[dis(i,j)-1] += 1


    print("\n".join(map(str, dist_l)))




def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(N, X, Y)

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

F=lambda:tuple(int(X)for X in input().split());H,W,N=F();S={F()for _ in[0]*N};T=set();Z=[0]*10;*R,=range(9)
for Y,X in S:
	for A in R:
		P=A,B=X-A%3,Y-A//3
		if(0<A<W-1)*(0<B<H-1)*(P not in T):T.add(P);Z[sum((B+C//3,A+C%3)in S for C in R)]+=1
Z[0]+=(H-2)*(W-2)-sum(Z);print(*Z,sep='\n')

### FIXED CODE ###

F=lambda:tuple(int(X)for X in input().split());H,W,N=F();S={F()for _ in[0]*N};T=set();Z=[0]*10;*R,=range(9)
for Y,X in S:
	for A in R:
		P=A,B=X-A%3,Y-A//3
		if(0<A<W-1)*(0<B<H-1)*(P not in T):T.add(P);Z[sum((B+C//3,A+C%3)in S for C in R)]+=1
Z[0]+=(H-2)*(W-2)-sum(Z);print(*Z,sep='\n')
### BUGGY CODE ###

import bisect
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


n = int(input())
a = list(map(int, input().split()))
a.sort()
index = bisect.bisect_left(a,a[-1]//2)
x = combinations_count(a[-1],a[index])
y = combinations_count(a[-1],a[index-1])
if x>y:
    print(a[-1],a[index])
else:
    print(a[-1],a[index-1])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = []
for i in range(n-1):
    b.append([abs(a[-1]/2 -a[i]),a[i]])
b.sort()
print(a[-1],b[0][1])