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

import math as mt 
MAXN = int(input())
MAXN+=1
spf = [0 for i in range(MAXN)] 
def sieve(): 
    spf[1] = 1
    for i in range(2, MAXN): 
        spf[i] = i 
    for i in range(4, MAXN, 2): 
        spf[i] = 2
    for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
        if (spf[i] == i): 
            for j in range(i * i, MAXN, i): 
                if (spf[j] == j): 
                    spf[j] = i 

def get(x): 
    ret = {}
    while (x != 1):
                try:
                    ret[spf[x]]+=1
                except:
                    ret[spf[x]]=1
               # print(x)
                x = x // spf[x] 
    p=1
    for i in ret.keys():
        p=p*(ret[i]+1)
    return p

sieve()
r=1
for i in range(2,MAXN):
    p=get(i)
    r+=i*p
print(r)


### FIXED CODE ###

MAX = int(input())
MAX+=1
factor = [0]*(MAX + 1); 
def generatePrimeFactors(): 
	factor[1] = 1;
	for i in range(2,MAX): 
		factor[i] = i; 
	for i in range(4,MAX,2): 
		factor[i] = 2; 

	i = 3; 
	while(i * i < MAX): 
		if (factor[i] == i): 
			j = i * i; 
			while(j < MAX): 
				if (factor[j] == j): 
					factor[j] = i; 
				j += i; 
		i+=1; 

def ca(n): 
	if (n == 1): 
		return 1; 
	ans = 1; 
	dup = factor[n]; 
	c = 1; 
	j = int(n / factor[n]); 
	while (j > 1): 
		if (factor[j] == dup): 
			c += 1; 
		else: 
			dup = factor[j]; 
			ans = ans * (c + 1); 
			c = 1; 
		j = int(j / factor[j]); 

	ans = ans * (c + 1); 
	return ans; 
generatePrimeFactors() 
r=1
for i in range(2,MAX):
    r+=i*ca(i)
print(r)
### BUGGY CODE ###

#"""
import sys
input = sys.stdin.readline
#"""

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*N]

dp = [[(0,[])]*T for _ in [0]*(N+1)]

for i in range(N):
    a,b = AB[i]
    for t in range(T):
        dp[i+1][t] = dp[i][t]
        if t-a>=0:
            if dp[i+1][t][0] < dp[i][t-a][0] + b:
                dp[i+1][t] = (dp[i][t-a][0]+b,dp[i][t-a][1]+[i])

ans0 = dp[N][-1][0]
ans = ans0
s = set(dp[N][-1][1])
for i in range(N):
    if i in s:continue
    ans = max(ans,ans0+AB[i][1])
print(ans)

### FIXED CODE ###

#"""
import sys
input = sys.stdin.readline
#"""

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*N]

dp = [[0 for _ in [0]*T] for _ in [0]*(N+1)]

for i in range(N):
    a,b = AB[i]
    for t in range(T):
        dp[i+1][t] = dp[i][t]
        if t-a>=0:
            dp[i+1][t] = max(dp[i+1][t],dp[i][t-a]+b)

s = []
t = T-1
for j in range(N-1,-1,-1):
    a,b = AB[j]
    while (dp[j+1][t] == dp[j+1][t-1]) and t>0:
        t -= 1
    if dp[j+1][t] == dp[j][t]:
        pass
    else:
        t -= a
        s.append(j)

ans0 = dp[N][-1]
ans = ans0
for i in range(N):
    if s and i==s[-1] :
        s.pop()
        continue
    ans = max(ans,ans0+AB[i][1])
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n, m = map(int, input().split())

    if n == 1:
        a = int(input())
        for i in range(m):
            a //= 2
        print(a)
        exit()

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

    for i in range(m):
        mx = max(a)
        a[a.index(mx)] //= 2
    print(sum(a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


def main():
    n, m = map(int, input().split())

    if n == 1:
        a = int(input())
        for i in range(m):
            a //= 2
        print(a)
        exit()

    a = (list(map(int, input().split())))
    heapq._heapify_max(a)

    for i in range(m):
        tmp = _heappop_max(a) // 2
        _heappush_max(a, tmp)

    print(sum(a))


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

import numpy as np
N,M=map(int, input().split())
A=np.array(list(map(int, input().split())))
for i in range(M):
    x=np.argmax(A)
    A[x]=A[x]//2
print(sum(A))

### FIXED CODE ###

import heapq

N,M = map(int, input().split())
A = list(-int(i) for i in input().split()) 

heapq.heapify(A)

for i in range(M):
    x=heapq.heappop(A)//(-2)
    heapq.heappush(A, -x)

print(-sum(A))
### BUGGY CODE ###

#ソートしてでかいやつから割引券使っていって、次に値段が高いやつよりも値段が低くなれば次にいく。
#これを繰り返せばいい。
#一周してもまだ割引券が余っていればもう一度ソートして同じことをする。
#途中で割引券がなくなれば終了して、合計を計算する。
#実際に買い物をする順番は気にしなくていい。どこで何枚使うのが最適かが分かればいい
#ということは割引券を使うたび毎回ソートする？

n,m = map(int,input().split())
A = list(map(int,input().split()))
#print(A)
A.sort(reverse=True)

while m!=0:
  M_A = max(A)
  A[0] = M_A //2
  m -= 1
  A.sort(reverse=True)
  
print(sum(A))  
  
  



### FIXED CODE ###

#ソートしてでかいやつから割引券使っていって、次に値段が高いやつよりも値段が低くなれば次にいく。
#これを繰り返せばいい。
#一周してもまだ割引券が余っていればもう一度ソートして同じことをする。
#途中で割引券がなくなれば終了して、合計を計算する。
#実際に買い物をする順番は気にしなくていい。どこで何枚使うのが最適かが分かればいい
#ということは割引券を使うたび毎回ソートする？
#毎回ソートしてるとやっぱりTLEになる。次に値段が高いやつよりも値段が低くなれば次にいく。でいい

#n,m = map(int,input().split())
#A = list(map(int,input().split()))
#print(A)
#A.sort(reverse=True)
#while m!=0:
#  while A[0] > A[1]:
 #   M_A = max(A)
  #  A[0] = M_A //2
   # m -= 1
  #A.sort(reverse=True)
#print(sum(A))

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=a[i]*(-1)
  
import heapq
#小さい順に並べる
heapq.heapify(a)
for j in range(m):
  # 最小値を取り出して-1をかけ,bとする。
  b=heapq.heappop(a)*(-1)
  # b//2に-1をかけて,aに入れる。
  heapq.heappush(a,(b//2)*(-1))
  #print(a)
c=sum(a)
print(c*(-1))
### BUGGY CODE ###

N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
mod=998244353
S=sum(A)

dp=[[0 for j in range(S+1)] for i in range(N)]
dp[0][0]=pow(2,N,mod)
dp[0][A[0]]=pow(2,N-1,mod)

for i in range(1,N):
    for j in range(S+1):
        dp[i][j]=(dp[i-1][j]+pow(2,mod-2,mod)*(j>=A[i])*dp[i-1][j-A[i]])%mod

if S%2==1:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[N-1][i]
        ans%=mod
    print(ans)
else:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[N-1][i]
        ans%=mod
    dp=[[0 for j in range(S+1)] for i in range(N)]
    dp[0][0]=1
    dp[0][A[0]]=1

    for i in range(1,N):
        for j in range(S+1):
            dp[i][j]=(dp[i-1][j]+(j>=A[i])*dp[i-1][j-A[i]])%mod
    ans+=3*dp[N-1][S//2]
    ans%=mod
    print(ans)

### FIXED CODE ###

N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
mod=998244353
inv=pow(2,mod-2,mod)
S=sum(A)

dp=[0 for j in range(S+1)]
sub=[0 for j in range(S+1)]
dp[0]=pow(2,N,mod)
dp[A[0]]=pow(2,N-1,mod)
sub[0]=1
sub[A[0]]=1

for i in range(1,N):
    for j in range(S,A[i]-1,-1):
        dp[j]=(dp[j]+inv*dp[j-A[i]])%mod
        sub[j]=(sub[j]+sub[j-A[i]])%mod

if S%2==1:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[i]
        ans%=mod
    print(ans)
else:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[i]
        ans%=mod
    ans+=3*sub[S//2]
    ans%=mod
    print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():
    X, Y, Z, K = map(int, readline().rstrip().split())
    A = list(map(int, readline().rstrip().split()))
    B = list(map(int, readline().rstrip().split()))
    C = list(map(int, readline().rstrip().split()))
    
    ab = [A[i] + B[j] for i in range(len(A)) for j in range(len(B))]
    ab = sorted(ab, reverse=True)[:K]

    abc = [ab[i] + C[j] for i in range(len(ab)) for j in range(len(C))]
    print(*sorted(abc, reverse=True)[:K], sep='\n')


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    X, Y, Z, K = map(int, readline().rstrip().split())
    A = list(map(int, readline().rstrip().split()))
    B = list(map(int, readline().rstrip().split()))
    C = list(map(int, readline().rstrip().split()))
    
    ab = [A[i] + B[j] for i in range(len(A)) for j in range(len(B))]
    ab = sorted(ab, reverse=True)[:K]

    abc = [ab[i] + C[j] for i in range(len(ab)) for j in range(len(C))]
    print(*sorted(abc, reverse=True)[:K], sep='\n')


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

from math import sqrt
n,m = (int(i) for i in input().split())
f = 1
for i in range(2,int(sqrt(m))+1):
	if m%i==0:
		f = 0
		break
if f: print(1)
else:
	for i in range(m//n,0,-1):
		if m%i==0: break
	print(i)

### FIXED CODE ###

from math import sqrt
from bisect import bisect
n,m = (int(i) for i in input().split())
x = []
for i in range(1,int(sqrt(m))+1):
	if m%i==0:
		x.append(i)
		x.append(m//i)
x.sort()
print(x[bisect(x,m//n)-1])
### BUGGY CODE ###

N = int(input())
H = list(map(int,input().split()))
ans = 0
cnt = 0
start = 0
for i in range(N):
    ans = max(ans,cnt)
    cnt = 0
    for j in range(N-i-1):
        if start > i:
          break
        if H[i+j] >= H[i+j+1]:
            cnt += 1
        else:
          start = j+1
          break    
print(ans)

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
ans = 0
cnt = 0
for i in range(N-1):
      if H[i] >= H[i+1]:
          cnt += 1
      else:
          ans = max(ans,cnt)
          cnt = 0
      if i+2 == N:
        print(max(ans,cnt))
        exit()
print(ans)
### BUGGY CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
a = []
for i in range(Q):
    a.append(map(int, raw_input().split()))
test_dict = {}
for j, temp in enumerate(a):
    #print(temp)
    str_sub = string[temp[0]-1:temp[1]]
    #print('j',j)
    if j == 0:
        test_dict[str_sub] = str_sub.count('AC')
        result = str(test_dict[str_sub])
        continue
    if test_dict.get(str_sub) and j >= 1:
        #print(test_dict.get(str_sub))
        result += '\n' + str(test_dict.get(str_sub))
        continue
    test_dict[str_sub] = str_sub.count('AC')
    result += '\n' + str(test_dict[str_sub])
    #print(test_dict[str_sub])
    #print('result', result)
print(result)

### FIXED CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
cnt = [0]
for i in range(N):
#    print(i)
#    print(string[i-2:i])
#    if i == 0:
#        cnt.append(0)
#        continue
    if string[i-1:i+1] == 'AC':
        cnt.append(cnt[i]+1)
        continue
    cnt.append(cnt[i])

for j in range(Q):
    #print(j)
    pare = map(int, raw_input().split())
    print(cnt[pare[1]] - cnt[pare[0]])
### BUGGY CODE ###

import math
import numpy as np

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

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

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    primeNum.append(1)
    return primeNum

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr[-1][0]

N=gcd(A,B)

if N==1:
    print(1)
else:
    ms = factorization(N)
    pl = seachPrimeNum(ms)
    ya = yakusuu(N)
    count=0
#    print(N,ms,pl,ya)
    for i in range(len(pl)):
        if pl[i] in ya:
            count+=1
    print(count)

### FIXED CODE ###

import collections

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

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

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

import sys
res = dict()
dll = [None] * 2000000
left = 0
right = 0
n = int(input())
for inpt in sys.stdin.read().splitlines():
    i = inpt.split()
    if i[0] == "insert":
        x = int(i[1])
        dll[left] = x
        if(x in res):
            res[x].append(left)
        else:
            res[x] = [left]
        left += 1
    if i[0] == "delete":
        x = int(i[1])
        if(x in res):
            ind = max(res[x])
            dll[ind] = None
            res[x].remove(ind)
            if(len(res[x]) == 0):
                del res[x]
            if(ind == (left - 1)):
                left = ind
            if(ind == right):
                right += 1
    if i[0] == "deleteFirst":
        left -= 1
        x = dll[left]
        res[x].remove(left)
        if(len(res[x]) == 0):
            del res[x]
        dll[left] = None
    if i[0] == "deleteLast":
        right += 1
    # print(dll[right:left])
ret = []
for x in dll[right:left]:
    if(x is not None):
        ret.append(str(x))
ret.reverse()
print(" ".join(ret))

### FIXED CODE ###

import sys
res = dict()
dll = [None] * 2000000
left = 0
right = 0
n = int(input())
for inpt in sys.stdin.read().splitlines():
    i = inpt.split()
    if i[0] == "insert":
        x = int(i[1])
        dll[left] = x
        if(x in res):
            res[x].add(left)
        else:
            res[x] = set([left])
        left += 1
    if i[0] == "delete":
        x = int(i[1])
        if(x in res):
            ind = max(res[x])
            dll[ind] = None
            res[x].remove(ind)
            if(len(res[x]) == 0):
                del res[x]
            if(ind == (left - 1)):
                left = ind
            if(ind == right):
                right += 1
    if i[0] == "deleteFirst":
        left -= 1
        x = dll[left]
        res[x].remove(left)
        if(len(res[x]) == 0):
            del res[x]
        dll[left] = None
    if i[0] == "deleteLast":
        right += 1
    # print(dll[right:left])
ret = []
for x in dll[right:left]:
    if(x is not None):
        ret.append(str(x))
ret.reverse()
print(" ".join(ret))
### BUGGY CODE ###

def e_friendships(N, K):
    if K > (N - 1) * (N - 2) // 2:
        return -1

    ans_graph = []
    for i in range(2, N + 1):
        ans_graph.append('{} {}'.format(1, i))  # スターの構成

    def append_edge(t, lst):
        count = 0
        while True:
            for i in range(2, N):
                for j in range(i + 1, N + 1):
                    lst.append('{} {}'.format(i, j))
                    count += 1
                    if count == t:
                        return lst

    ans_graph = append_edge((N - 1) * (N - 2) // 2 - K, ans_graph)
    return str(len(ans_graph)) + '\n' + '\n'.join(ans_graph)

N, K = [int(i) for i in input().split()]
print(e_friendships(N, K))

### FIXED CODE ###

def e_friendships(N, K):
    if K > (N - 1) * (N - 2) // 2:
        return -1

    ans_graph = []
    for i in range(2, N + 1):
        ans_graph.append('{} {}'.format(1, i))  # スターの構成

    def append_edge(t, lst=[]):
        count = 0
        for i in range(2, N):
            for j in range(i + 1, N + 1):
                if count == t:
                    return lst
                lst.append('{} {}'.format(i, j))
                count += 1
        return lst

    ans_graph = append_edge((N - 1) * (N - 2) // 2 - K, ans_graph)
    return str(len(ans_graph)) + '\n' + '\n'.join(ans_graph)

N, K = [int(i) for i in input().split()]
print(e_friendships(N, K))
### BUGGY CODE ###

N, K = map(int, input().split())
MOD = 998244353

nums = []

for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        nums.append(j)
nums.sort()
# print(nums)


dp = [0] * (N + 1)
dp[1] = 1
for i in range(2, N + 1):
    for n in nums:
        if i > n:
            dp[i] += dp[i - n] % MOD
        else:
            break

print(dp[-1]%MOD)


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353

nums = []

for i in range(K):
    l, r = map(int, input().split())
    nums.append([l, r])
# nums.sort()
# print(nums)


dp = [0] * (N + 1)
dp[1] = 1
cumsum = [0, 1]

for i in range(2, N + 1):
    for l, r in nums:
        # print(l,r)
        if i - l > 0:
            # print(i, l, r)
            # r = min(r, N)
            dp[i] += (cumsum[i - l] - cumsum[max(i - r - 1, 0)]) % MOD
    cumsum.append(cumsum[-1] + dp[i])

print(dp[-1] % MOD)
# print(dp)
# print(cumsum)
### BUGGY CODE ###

n, m, q = map(int,input().split())
t = [list(map(int,input().split())) for i in range(m)]
cond = [list(map(int,input().split())) for j in range(q)]
for i in range(q):
    cond1 = [1 if t[j][0] >= cond[i][0] and t[j][1] <= cond[i][1] else 0 for j in range(m)]
    print(sum(cond1))
    

### FIXED CODE ###

import numpy as np
import sys

N, M, Q = map(int, input().split())

I = sys.stdin.read().split()

L,R = np.array(I[:2*M], np.int32).reshape([2,-1], order='F')
p,q = np.array(I[2*M:], np.int32).reshape(2,-1, order='F')
d = np.zeros([N+1, N+1], np.int32)

d = np.zeros([1+N, 1+N], np.int32)
np.add.at(d, (N-L,R), 1)

d = np.add.accumulate(d, axis = 1)
d = np.add.accumulate(d)

ans = d[N-p,q]

for a in ans:
	print(a)
### BUGGY CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
S=[]
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	for k in range(1,N+1):
		S.append(sum(P[0:k]))
	T=[S[K-1]]
	for n in range(0,N-K):
		T.append(S[n+K]-S[n])
	print((max(T)+K)/2)


### FIXED CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	T=sum(P[0:(K)])
	S=sum(P[0:(K)])
	for k in range(0,N-K):
		S=S-P[k]+P[k+K]
		if T<=S:
			T=S
		else:
			continue
	print((T+K)/2)
### BUGGY CODE ###

n,k = map(int,input().split())
hlist = list(map(int,input().split()))
dp = [float('inf')]*n
dp[0] = 0
dp[1] = abs(hlist[1]-hlist[0])
for i in range(2,n):
  for j in range(i):
    if i-j <= k:
      dp[i] = min(dp[i], dp[j] + abs(hlist[i]-hlist[j]))
print(dp[n-1])

### FIXED CODE ###

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

dp = [10**9]*n
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i-j >= 0:
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[n-1])
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c % 2, b-1))
        edge[b-1].append((c % 2, a-1))

    dist = [-1]*N
    color = [-1]*N

    def dfs(v, G):
        todo = []
        dist[v] = 0
        color[v] = 0
        todo.append(v)
        while todo:
            u = todo[-1]
            for c, next_v in G[u]:
                if dist[next_v] != -1:
                    continue
                dist[next_v] = dist[u] + c
                if dist[next_v] % 2 == 1:
                    color[next_v] = 1
                else:
                    color[next_v] = 0
                todo.append(next_v)
                break
            else:
                todo.pop()

    dfs(0, edge)
    print(*color, sep="\n")
    # print("\n", *dist, sep="\n")


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N+1)]
    st = 0
    st_w = 0
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v, w))
        G[v].append((u, w))
        if i == 0:
            st = u
            st_w = w
    color = [-1] * (N+1)  # 0: white, 1: black, -1: undefined
    from collections import deque

    def coloring(v, w):
        """
        breadth-first search
        a simplified version
        """
        que = deque()
        color[v] = 0
        que.append((v, w))
        while que:
            u, w = que.popleft()
            for v, d in G[u]:
                if color[v] != -1:
                    continue
                if d % 2 != 0:
                    n_col = (color[u] + 1) % 2
                else:
                    n_col = color[u]
                color[v] = n_col
                que.append((v, d))

    coloring(st, st_w)
    for c in color[1:]:
        print(c)


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

int_n = int(input())
ar_int_a = list(map(int, input().split()))

result = []

ar_int_a.sort(reverse=True)

headers = set(ar_int_a)

counters = [{'number': i, 'count': ar_int_a.count(i)} for i in headers
            if ar_int_a.count(i) >= 2]

for i in sorted(counters, key=lambda x: x['number'], reverse=True):

    if len(result) == 0 and i['count'] >= 4:
        print(i['number'] ** 2)
        exit(0)
    elif len(result) < 2:
        result.append(i['number'])
    else:
        break
if len(result) == 2:
    print(result[0] * result[1])
else:
    print(0)



### FIXED CODE ###

import collections

int_n = int(input())
ar_int_a = list(map(int, input().split()))

c = collections.defaultdict(int)
result = []

for a in ar_int_a:
    c[a] += 1

for k in sorted(c.keys(), key=lambda x: x, reverse=True):
    if len(result) == 0 and c[k] >= 4:
        print(k ** 2)
        exit(0)
    elif len(result) < 2 and c[k] >= 2:
        result.append(k)

    if len(result) == 2:
        print(result[0] * result[1])
        exit(0)
else:
    print(0)
### BUGGY CODE ###

n  = int(input())
arr = [int(i) for i in input().split()]
arr.sort()

works= lambda a,b,c : (a<(b+c)) and (b<(a+c)) and (c<(b+a))

total = 0

for i in range(n):
    aI = arr[i]
    for j in range(i):
        aJ = arr[j]
        for k in range(j):
            if works(arr[k],aI,aJ):
                total+=1

print(total)


### FIXED CODE ###

n  = int(input())
arr = [int(i) for i in input().split()]
arr.sort()

total = 0

for i in range(n-2):
    aI = arr[i]
    k = i + 2
    
    for j in range(i+1,n):
        mySum = aI+arr[j]

        while (k<n) and arr[k]<mySum:
            k+=1
            
        if k>j:
            total+= k-j-1

print(total)
### BUGGY CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] == A[i][k] + A[k][j]:
                break
            elif A[i][k] > A[i][j] + A[j][k]:
                print(-1)
                exit()
        else:
            ans += A[i][j]

print(ans)

### FIXED CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] == A[i][k] + A[k][j]:
                break
            elif A[i][k] > A[i][j] + A[j][k]:
                print(-1)
                exit()
        else:
            ans += A[i][j]

print(ans)