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

from collections import deque

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]

g = {i:[] for i in range(n+1)}

for a,b in ab:
    g[a].append(b)
    g[b].append(a)
    
seen = {i:0 for i in range(n+1)}
seen[0]=1
seen[1]=1
q = deque()
q.append(1)
grpsize=1

while 0 in seen.values():
    if len(q)>0:
        now = q.popleft()
        nextp = g[now]
        for i in nextp:
            if seen[i]==0:
                q.append(i)
                grpsize+=1
                seen[i]=grpsize
        
    else:
        for i in range(1,n+1):
            if seen[i]==0:
                grpsize=1
                seen[i]=grpsize
                q.append(i)
                break
                
print(max(seen.values()))

### FIXED CODE ###

from sys import setrecursionlimit

def find(par,i):
    if par[i]<0:
        return i
    par[i] = find(par,par[i])
    return par[i]

def unite(par,i,j):
    ri = find(par,i)
    rj = find(par, j)
    if ri==rj:
        return
    par[rj] += par[ri]
    par[ri] = rj
    
setrecursionlimit(10**6)
n,m = map(int,input().split())

parent = [-1]*n
for _ in range(m):
    a,b = map(lambda x:int(x)-1,input().split())
    unite(parent,a,b)
    
print(-min(parent))
### BUGGY CODE ###

n, m = map(int, input().split())
ans = 1
for i in range(n, int(m ** .5) + 1):
    if m % i == 0:
        print(m // i)
        exit()
for i in range(1, m // 2 + 1):
    if m % i == 0:
        if m // i >= n:
            ans = i
        else:
            break
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
ans = 1
for i in range(1, int(m ** .5) + 1):
    if m % i == 0:
        b = m // i
        if i * n <= m:
            ans = max(ans, i)
        if b * n <= m:
            ans = max(ans, b)
print(ans)
### BUGGY CODE ###

N, M, Q = map(int, input().split())
coordinate = [[0 for _ in range(N)] for i in range(N)]
for m in range(M):
    l, r = map(int, input().split())
    coordinate[l-1][r-1] += 1

for k in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p-1, q):
        for j in range(p-1, q):
            ans += coordinate[i][j]
    print(ans)

### FIXED CODE ###

N, M, Q = map(int, input().split())
coordinate = [[0 for _ in range(N+1)] for i in range(N+1)]
for m in range(M):
    l, r = map(int, input().split())
    coordinate[l-1][r-1] += 1

for i in range(N):
    for j in range(1, N):
        coordinate[i][j] += coordinate[i][j-1]


for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p-1, q):
        ans += coordinate[i][q-1] - coordinate[i][p-2]
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat May 25 21:57:15 2019

@author: Yamazaki Kenichi
"""
import bisect

Q = int(input())
Q2 = [input() for i in range(Q)]

ans = []
A = []
B = 0
C = 0
counta = 0
d, prea, b = map(int,Q2[0].split()) 
for q in Q2:
    if q[0] == '1':
#        input
        d, a, b = map(int,q.split()) 
        bisect.insort_left(A,a)
#        if A[(len(A)-1)//2] > a:
#            C = abs(prea - a)
#        else:
#            C = abs(A[(len(A)-1)//2] - a)
        C = abs(A[(len(A)-1)//2] - a) if counta % 2 == 0 else abs(prea - a)
        B += (b + C)
#        C = abs(prea - a)
        prea = A[(len(A)-1)//2]
        counta += 1
    else:
#        output
        tmp = A[(len(A)-1)//2]
        ans.append([tmp,B])
for c in ans:
    print(' '.join(map(str,c)))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue May 28 22:22:21 2019

@author: Yamazaki Kenichi
"""
import heapq

Q = int(input())
Q2 = [input() for i in range(Q)]

ans = []
Al,Ar = [-(-(10**9+1))],[10**9+1]
B = 0
flg = False
for q in Q2:
    if q[0] == '1':
#        input
        d, a, b = map(int,q.split())
        if not flg:
            heapq.heappush(Al,-a)
            B += b
            flg = True
            continue
        
#        C = abs(a - (-Al[0]))
        if len(Al) == len(Ar):
            if a < Ar[0]:
#                C = abs(a - (-Al[0]))
                heapq.heappush(Al,-a)
#                C = abs(a - (-Al[0]))
#            elif a < Ar[0]:
#                heapq.heappush(Al,-(heapq.heappop(Ar)))
#                heapq.heappush(Ar,a)
                C = abs(a - (-Al[0]))
            else:
                heapq.heappush(Ar,a)
                heapq.heappush(Al,-(heapq.heappop(Ar)))
                C = abs(a - (-Al[0]))
        else:
            if a < Ar[0]:
                C = abs(a - (-Al[0]))
                heapq.heappush(Al,-a)
                heapq.heappush(Ar,-(heapq.heappop(Al)))
#                C = abs(a - (-Al[0]))
#            elif a < A[]
            else:
                C = abs(a - (-Al[0]))
                heapq.heappush(Ar,a)
#                C = abs(a - (-Al[0]))
        B += (b + C)
#        print(Al,Ar,a,B,b)
    else:
#        output
        ans.append([(-Al[0]),B])
        
for c in ans:
    print(' '.join(map(str,c)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
import datetime
import itertools
import sys
import copy

# 入力
#N = int(input())
#S = str(input())
#N, A, B = map(int, input().split())

N, W = map(int, input().split())
H = []
for _ in range(N) :
  H.append(list(map(int, input().split())))
#print(H)

#N(i+1)個目の品物を追加したときにWjとなる場合のWj地点の最大価値
dp = [0 for _ in range(W+1)]

for i in range(N) :
  dptemp = copy.deepcopy(dp)
  for j in range(W+1) :
    if dptemp[j] > 0 and j+H[i][0] <= W:
      dp[j+H[i][0]] = max(dptemp[j+H[i][0]], dptemp[j] + H[i][1])
    
  dp[H[i][0]] = max(dptemp[H[i][0]], H[i][1])
  #print (dp)      
#print (dp)

print (max(dp))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
import datetime
import itertools
import sys
import copy

# 入力
#N = int(input())
#S = str(input())
#N, A, B = map(int, input().split())

N, W = map(int, input().split())
H = []
for _ in range(N) :
  H.append(list(map(int, input().split())))
#print(H)

#N(i+1)個目の品物を追加したときにWjとなる場合のWj地点の最大価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1, N+1) :
  for j in range(W+1) :
    dp[i][j] = max(dp[i-1][j], dp[i][j])
    if dp[i-1][j] > 0 and j+H[i-1][0] <= W:
      dp[i][j+H[i-1][0]] = max(dp[i-1][j+H[i-1][0]], dp[i-1][j] + H[i-1][1])
    
  dp[i][H[i-1][0]] = max(dp[i-1][H[i-1][0]], H[i-1][1])
  #print (dp[i])      
#print (dp)

print (max(dp[N]))
### BUGGY CODE ###

n = int(input())
s = input()
ls = s[:n:]
rs = s[:n-1:-1]
dl = dict()
dr = dict()

for i in range(2**n):
    lr = ""
    rr = ""
    lb = ""
    rb = ""
    ii = i
    for j in range(n):
        if ii%2 == 1:
            lr += ls[j]
            rr += rs[j]
        else:
            lb += ls[j]
            rb += rs[j]
        ii >>= 1
    dl[(lr,lb)] = dl.get((lr,lb),0)+1
    dr[(rr,rb)] = dr.get((rr,rb),0)+1

ans = 0
for dlk,dlv in dl.items():
    ans += dlv*dr.get(dlk,0)

print(ans)


### FIXED CODE ###

#https://atcoder.jp/contests/agc026/submissions/10971924を参考にした

from collections import defaultdict
n = int(input())
s = input()
ls = s[:n:]
rs = s[:n-1:-1]
d = defaultdict(int)

def full_research(sa,r,b,t):
    if t == n:
        d[(r,b)] += 1
        return
    full_research(sa,r+sa[t],b,t+1)
    full_research(sa,r,b+sa[t],t+1)

full_research(ls,"","",0)
dl = d
d = defaultdict(int)
full_research(rs,"","",0)

ans = 0
for dlk,dlv in dl.items():
    ans += dlv*d[dlk]

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

from collections import Counter
N=int(input())
S=[0]*5000
S=list(input())

S_count=Counter(S)
r=S_count["R"]
g=S_count["G"]
b=S_count["B"]

ans=0

for i in range(N-2):
    for j in range(1,N):
        if i+2*j>=N:
            continue
        if S[i]!=S[i+j] and S[i+j]!=S[i+2*j] and S[i]!=S[i+2*j]:
            ans+=1

print(r*g*b-ans)

### FIXED CODE ###

from collections import Counter
N=int(input())
S=[0]*5000
S=list(input())

S_count=Counter(S)
r=S_count["R"]
g=S_count["G"]
b=S_count["B"]

ans=0

for i in range(N-2):
    for j in range(1,N):
        if i+2*j>=N:
            break
        if S[i]!=S[i+j] and S[i+j]!=S[i+2*j] and S[i]!=S[i+2*j]:
            ans+=1

print(r*g*b-ans)
### BUGGY CODE ###

import itertools
n,m = map(int,input().split())
zahyou_list = [i for i in map(int,input().split())]
zahyou_list.sort()
#print(zahyou_list)
kaisa_list = []
#print(sum(kaisa_list))

for i in range(len(zahyou_list)-1):
    kaisa_list.append(zahyou_list[i+1] - zahyou_list[i])
mini = sum(kaisa_list)
#print(kaisa_list)
if n >= m:
    print(0)
else:
    #コマの数が少ない時は全体から引く
    if (m-1)/2 >= n-1:
        for v in itertools.combinations(kaisa_list,n-1):
            #print(v)
            #print(mini)
            #print(sum(kaisa_list)-sum(v))
            mini = min(mini,sum(kaisa_list)-sum(v))
        print(mini)
    else:
        #コマの数が多い時は要素を足し合わせる
        for v in itertools.combinations(kaisa_list,m-n):
            #print(v)
            mini = min(mini,sum(v))
        print(mini)

"""
階差のリストのうちn-1個要素を減らして合計値の最小値で求める

"""


### FIXED CODE ###

import itertools
n,m = map(int,input().split())
zahyou_list = [i for i in map(int,input().split())]
zahyou_list.sort()
#print(zahyou_list)
kaisa_list = []

#print(sum(kaisa_list))

for i in range(len(zahyou_list)-1):
    kaisa_list.append(zahyou_list[i+1] - zahyou_list[i])
mini = sum(kaisa_list)
kaisa_list.sort()
#print(kaisa_list)
if n >= m:
    print(0)
elif n == 1:
    print(sum(kaisa_list))
else:
    print(sum(kaisa_list[:-(n-1)]))
### BUGGY CODE ###

import bisect

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

mem =[]
count =0

for i in range(N-1,-1,-1):
    count += bisect.bisect_right(mem,A[i]+i)-bisect.bisect_left(mem,A[i]+i)
    bisect.insort(mem,i-A[i])

print(count)

### FIXED CODE ###

import bisect

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

mem =[0 for i in range(0,N +1,1)]
count =0

for i in range(N-1,-1,-1):
    if A[i]+i < N:
        count+=mem[A[i]+i]

    if i - A[i] > 0:
        mem[i - A[i]]+=1

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

def main():
    N,W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]

    dp = [list([0] * (W+1)) for _ in range(N)]
    dp[0][wv[0][0]] = wv[0][1]

    for i in range(1,N):
        w = wv[i][0]
        if W < w:
            continue
        v = wv[i][1]
        for j in range(W+1):
            sum_w = j + w
            if sum_w <= W:
                dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][j] + v)
            dp[i][j] = max(dp[i][j],dp[i-1][j])

    print(max(dp[-1]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N,W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]

    dp = [list([0] * (W+1)) for _ in range(N)]
    dp[0][wv[0][0]] = wv[0][1]

    for i in range(1,N):
        w = wv[i][0]
        if W < w:
            continue
        v = wv[i][1]
        for j in range(W+1):
            sum_w = j + w
            if sum_w <= W:
                dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][j] + v)
            dp[i][j] = max(dp[i][j],dp[i-1][j])

    print(max(dp[-1]))

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

N = int(input())

arr = []
for i in range(N):
    arr.append(str(input()))

count = 0

def sort_str(s):
    return "".join(sorted(list(s)))

for i, item in enumerate(arr):
    s = sort_str(item)
    for j in range(i+1, N):
        if sort_str(arr[j]) == s:
            count += 1

print(count)

### FIXED CODE ###

N = int(input())

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

m = {}

def sort_str(s):
    return "".join(sorted(list(s)))

for i in range(N):
    s = str(input())
    ss = sort_str(s)

    if ss in m:
        m[ss] += 1
    else:
        m[ss] = 1


count = 0

for c in m.values():
    if c > 1:
        count += cmb(c, 2)

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

N=input()
S=input()
Sn=[]
R=0
G=0
B=0
for i in range(len(S)):
    if S[i]=='R':
        R+=1
        Sn.append(1)
    elif S[i]=='G':
        G+=1
        Sn.append(2)
    else:
        B+=1
        Sn.append(3)

count=0
for start in range(len(S)):
        for diff in range(1,int((len(S)-start+1)/2)):
            if (Sn[start]-Sn[start+diff])*(Sn[start+diff]-Sn[start+(2*diff)])*(Sn[start]-Sn[start+(2*diff)])!=0: 
                count+=1
                
print(str((R*G*B)-count))

### FIXED CODE ###

N=input()
S=input()
Sn=[]
R=0
G=0
B=0
for i in range(len(S)):
    if S[i]=='R':
        R+=1
        Sn.append(1)
    elif S[i]=='G':
        G+=1
        Sn.append(2)
    else:
        B+=1
        Sn.append(3)

count=0
for start in range(len(S)):
        for diff in range(1,int((len(S)-start+1)/2)):
            #int(start,diff)
            if (Sn[start]-Sn[start+diff])*(Sn[start+diff]-Sn[start+(2*diff)])*(Sn[start]-Sn[start+(2*diff)])!=0: 
                count+=1
                
print(str((R*G*B)-count))
### BUGGY CODE ###

N = int(input())
P = list(input())
X = 100000000
for i in range(N):
    x = (P[:i].count("W")+P[i+1:].count("E"))
    if x < X:
        X = x
print(X)

### FIXED CODE ###

N = int(input())
P = list(input())
X = P[1:].count("E")
a = [X]
for i in range(N-1):
    if P[i] == "W":
        X += 1
    if P[i+1] == "E":
        X -= 1
    a.append(X)

print(min(a))
### BUGGY CODE ###

from math import fabs
N=int(input())
pos=list(map(int,input().split()))

for i in range(N):
    pos_=pos.copy()
    del pos_[i]
    pos_.insert(0,0)
    pos_.insert(N+1,0)
    x=0
    for j in range(N):
        x+=fabs(pos_[j+1]-pos_[j])
    print(int(x))
    

### FIXED CODE ###

from math import fabs
N=int(input())
pos=list(map(int,input().split()))
pos.insert(0,0)
pos.insert(N+1,0)
total_len=0
for i in range(N+1):
    total_len+=fabs(pos[i+1]-pos[i])
    

for i in range(N):
    total=total_len-fabs(pos[i+1]-pos[i])-fabs(pos[i+2]-pos[i+1])+fabs(pos[i+2]-pos[i])
    print(int(total))
### BUGGY CODE ###

from bisect import bisect_left
import numpy as np

N, M, *A = map(int, open(0).read().split())
A.sort()


def calc(t):
    cnt = 0
    for ai in A:
        cnt += N - bisect_left(A, t - ai)
    if M <= cnt:
        return True
    else:
        return False


def solve():
    left, right = 0, 2 * 10 ** 5 + 1
    while 1 < right - left:
        mid = (left + right) // 2
        if calc(mid):
            left = mid
        else:
            right = mid
    
    ans = 0
    add_cnt = 0
    for ai in A:
        index = bisect_left(A, left - ai)
        if index == N:
            continue
        add_cnt += N - index
        ans += (N - index) * ai + np.cumsum(A[index:])[-1]
    ans -= left * (add_cnt - M)
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from bisect import bisect_left

N, M, *A = map(int, open(0).read().split())
A.sort()


def calc(t):
    cnt = 0
    for ai in A:
        cnt += N - bisect_left(A, t - ai)
    if M <= cnt:
        return True
    else:
        return False


def solve():
    left, right = 0, 2 * 10 ** 5 + 1
    while 1 < right - left:
        mid = (left + right) // 2
        if calc(mid):
            left = mid
        else:
            right = mid
    
    sum_A = [0] * N
    sum_A[-1] = A[-1]
    for i in range(N - 2, -1, -1):
        sum_A[i] = sum_A[i + 1] + A[i]
    
    ans = 0
    add_cnt = 0
    for ai in A:
        index = bisect_left(A, left - ai)
        if index == N:
            continue
        add_cnt += N - index
        ans += (N - index) * ai + sum_A[index]
    ans -= left * (add_cnt - M)
    print(ans)


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

a, b = map(int, input().split())
res = 1
for i in range(a, b + 1):
    res *= i
print('Positive' if res > 0 else 'Negative' if res < 0 else 'Zero')

### FIXED CODE ###

a, b = map(int, input().split())

if a <= 0 <= b:
    print('Zero')
elif 0 < a:
    print('Positive')
elif (b - a + 1)%2 == 0:
    print('Positive')
else:
    print('Negative')
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

max_comb = None
max_value = 0


def memorize(c, value, memo):
    global max_comb
    global max_value

    memo[c] = value
    if max_value < memo[c]:
        max_value = memo[c]
        max_comb = c


def comb(a_i, a_j, memo):
    c = (a_i, a_j)
    # print(a_i, a_j)

    if c in memo:
        return memo[c]

    if a_j == 1:
        memorize(c, a_i, memo)
        return a_i

    if a_i == a_j or a_j == 0:
        memorize(c, 1, memo)
        return 1

    value = comb(a_i - 1, a_j, memo) + comb(a_i - 1, a_j - 1, memo)
    memorize(c, value, memo)
    return memo[c]


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    # n = 5
    # a = [6, 9, 4, 2, 11]
    a_sorted = sorted(a, reverse=True)

    memo = dict()
    for i in range(n - 1):
        for j in range(i + 1, n):
            comb(a_sorted[i], a_sorted[j], memo)

            # print("comb:", a_sorted[i], a_sorted[j])

    print(max_comb[0], max_comb[1])


### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    # n = 5
    # a = [6, 9, 4, 2, 11]

    max_a = max(a)
    max_half = max_a / 2

    best_a_j = a[0] if a[0] != max_a else a[1]
    min_d = max_half
    for a_j in a:
        if a_j == max_a:
            continue

        d = abs(a_j - max_half)
        if d < min_d:
            best_a_j = a_j
            min_d = d

    print(max_a, best_a_j)
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x + y + z == s:
        ans += 1
print(ans)

### FIXED CODE ###

k,n = map(int,input().split())
ans = 0
for i in range(k+1):
  for j in range(k+1):
    if 0 <= n-i-j <= k:
      ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())
p_list = list(map(int,input().split()))
ans = 0
for i in range(n):
    if min(p_list[:i+1]) >= p_list[i]:
        ans += 1
print(ans)    

### FIXED CODE ###

n = int(input())
p_ls = list(map(int,input().split()))
min_ = float('inf')
count = 0
for i in range(n):
    if p_ls[i] < min_:
        count += 1
        min_ = p_ls[i]
print(count)
### BUGGY CODE ###

a,b,c,k=map(int,input().split())
if a==b==c:
    print ('0')
    exit ()
for _ in range(k):
    a,b,c=(b+c),(a+c),(a+b)
ans=a-b
if ans>10**18:
    print ('Unfair')
else:
    print(ans)

### FIXED CODE ###

a,b,c,k=map(int,input().split())
ans=0
if k%2==0:
    ans=a-b
else:
    ans=b-a
if ans>10**18:
  print ('Unfair')
else:
  print (ans)
### BUGGY CODE ###

n,k,q,*a=map(int,open(0).read().split())
s=sorted
m=1e18
for b in a:
    i=[i for i,t in enumerate(a)if t<b]
    l=s(u for t in[s(a[i+1:j])[::-1][k-1:]for i,j in zip([-1]+i,i+[n])]for u in t)
    if len(l)>=q:m=min(m,l[q-1]-b)
print(m)

### FIXED CODE ###

n,k,q,*a=map(int,open(0).read().split())
s=sorted
m=1e18
for b in a:
    i=[i for i,t in enumerate(a)if t<b]
    l=s(u for t in[s(a[i+1:j])[::-1][k-1:]for i,j in zip([-1]+i,i+[n])]for u in t)
    if len(l)>=q:m=min(m,l[q-1]-b)
print(m)
### BUGGY CODE ###

from math import factorial
N, M, K = map(int, input().split())

MOD = 10**9+7

def comb(n, r):
    r = n-r if n-r < r else r
    if r == 0:
        return 1
    ndfact = 1
    for i in range(n, n-r, -1):
        ndfact *= i
    return ndfact // factorial(r)

p = comb(N*M-2, K-2)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt
        #if ans > DIV:
        #    ans %= DIV
        #print(ans)

print((ans*p)%MOD)


### FIXED CODE ###

from math import factorial
N, M, K = map(int, input().split())

MOD = 10**9+7

fact = [1] * (N*M+1)
for i in range(2, N*M+1):
    fact[i] = fact[i-1] * i % MOD

def comb(n, r):
    r = n-r if n-r < r else r
    return fact[n] * pow(fact[r], MOD-2, MOD) * pow(fact[n-r], MOD-2, MOD) % MOD

p = comb(N*M-2, K-2)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt % MOD
ans = ans * p % MOD

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

n,k = map(int,input().split())
s = input()
tmp = s[0]
cnt = 1
ans = 0
ss = []
if s[0] == '0':
    ss.append(0)

for i in range(1,n):
    if s[i] == tmp:
        cnt += 1
    else:
        tmp = s[i]
        ss.append(cnt)
        cnt = 1
ss.append(cnt)
if s[-1] == '0':
    ss.append(0)
ll = len(ss)

if k >= ll//2:
    print(n)
else:
    for i in range(ll-k*2)[::2]:
        ans = max(ans, sum(ss[i:i+k*2+1]))
    print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
s = input()
tmp = s[0]
cnt = 1
ans = 0
ss = []
res = [0]
sum = 0
if s[0] == '0':
    ss.append(0)

for i in range(1,n):
    if s[i] == tmp:
        cnt += 1
    else:
        tmp = s[i]
        ss.append(cnt)
        cnt = 1
ss.append(cnt)
if s[-1] == '0':
    ss.append(0)
ll = len(ss)
for i in range(ll):
    sum += ss[i]
    res.append(sum)

if ll//2 <= k:
    print(n)
else:
    for i in range(ll-k*2)[::2]:
        ans = max(ans, res[i+k*2+1]-res[i])
    print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=''
for i in range(1,n+1):
    ans+=str(a.index(i)+1)+' '

print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    b[a[i]-1]=str(i+1)

print(' '.join(b))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**6)

n, q = map(int, input().split())

path = [[] for _ in range(n + 1)]
for i in range(n - 1):
  a, b = map(int, input().split())
  path[a].append(b)
  path[b].append(a)

plus = [0] * (n + 1)

for _ in range(q):
  p, x = map(int, input().split())
  plus[p] += x

def calc(num, path, plus, parent):
  for i in path[num]:
    if i == parent:
      continue

    plus[i] += plus[num]
    calc(i, path, plus, num)

calc(1, path, plus, 0)

print(" ".join([str(i) for i in plus[1:]]))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)

n, q = map(int, sys.stdin.readline().strip().split())

path = [[] for _ in range(n + 1)]
for i in range(n - 1):
  a, b = map(int, input().split())
  path[a].append(b)
  path[b].append(a)

plus = [0] * (n + 1)

for _ in range(q):
  p, x = map(int, sys.stdin.readline().strip().split())
  plus[p] += x

def calc(num, path, plus, parent):
  for i in path[num]:
    if i == parent:
      continue

    plus[i] += plus[num]
    calc(i, path, plus, num)

calc(1, path, plus, 0)

print(" ".join([str(i) for i in plus[1:]]))
### BUGGY CODE ###

k=int(input())
a=[]
count=1
if k%2==0:
    print(-1)
else:
    ai=7%k
    while 1:
        if ai==0:
            print(count)
            break
        elif ai in a:
            print(-1)
            break
        else:
            a.append(ai)
            ai=(ai*10+7)%k
            count+=1




### FIXED CODE ###

#正答
k=int(input())
a=set()
count=1
if k%2==0:
    print(-1)
else:
    #下の桁に７を足していく
    ai=7%k
    while 1:
        if ai==0:
            print(count)
            break
        elif ai in a:
            print(-1)
            break
        else:
            a.add(ai)
            ai=(ai*10+7)%k
            count+=1
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
import math
b=a.copy()
b=sorted(b,reverse=True)
comb_n=max(b)
b.pop(0)
c=b
def comb(n,r):
    return math.factorial(n)//((math.factorial(r))*(math.factorial(n-r)))
        
comb_list=[]
ind_list=[]
for i in c:
    comb_list.append(comb(comb_n,i))
    ind_list.append(i)
max_num=max(comb_list)
for i in range(len(comb_list)):
    if comb_list[i]==max_num:
        print(comb_n,ind_list[i])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(a,reverse=True)
comb_n=a[0]
a=a[1:]
r_ind=int(comb_n/2)

ans=0
for i in range(len(a)-1):
     if abs(a[i]-r_ind)<=abs(a[i+1]-r_ind):
          ans=a[i]
          break
print(comb_n,ans)