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

n = int(raw_input())
a = raw_input().split()

cnt = 0
for i in a:
    a[cnt] = int(i)
    cnt += 1

chk = {}
chk2 = {}
def make_divisors(k):
    divisors = []
    for i in range(1, int(k**0.5)+1):
        if k % i == 0:
            if i in chk:
                chk[i] += 1
            else:
                chk[i] = 1
            if i != k // i:
                key = int(k//i)
                if key in chk:
                    chk[key] += 1
                else:
                    chk[key] = 1
    return divisors

for i in range(2):
    make_divisors(a[i])
cnt = 1
for i in range(2,len(a)):
    k = a[i]
    if k in chk:
        make_divisors(k)
        cnt += 1
        continue
    del_list = []
    for j in chk:
        if k % j == 0:
            chk[j] += 1
        if chk[j] < cnt+1:
            del_list.append(j)
    for j in del_list:
        del chk[j]
    cnt += 1

answer = 0
for i in chk:
    if int(chk[i]) >= chk[1] - 1 and i > answer:
        answer = i
print answer

### FIXED CODE ###

n = int(raw_input())
a = raw_input().split()

cnt = 0
for i in a:
    a[cnt] = int(i)
    cnt += 1

chk = {}
chk2 = {}
def make_divisors(k):
    divisors = []
    for i in range(1, int(k**0.5)+1):
        if k % i == 0:
            if i in chk:
                chk[i] += 1
            else:
                chk[i] = 1
            if i != k // i:
                key = int(k//i)
                if key in chk:
                    chk[key] += 1
                else:
                    chk[key] = 1
    return divisors

for i in range(2):
    make_divisors(a[i])
cnt = 1
for i in range(2,len(a)):
    k = a[i]
    if k not in chk2:
        chk2[k] = 1
    else:
        if chk2[k] == 1:
            chk2[k] += 1
        elif chk2[k] > 1:
            continue
    del_list = []
    for j in chk:
        if k % j == 0:
            chk[j] += 1
        if chk[j] < cnt+1:
            del_list.append(j)
    for j in del_list:
        del chk[j]
    cnt += 1

answer = 0
for i in chk:
    if int(chk[i]) >= chk[1] - 1 and i > answer:
        answer = i
print answer
### BUGGY CODE ###

from sys import stdin
n, m = map(int, stdin.readline().rstrip().split())
ary = list(map(int, stdin.readline().rstrip().split()))
dp = [[float('inf')] * (m+1) for _ in range(n)]

for i in range(m, -1, -1):
    dp[n-1][i] = ary[n-1] // (2 ** i)
    if n == 1:
        break

if n >= 2:
    for j in range(n-2, -1, -1):
        for i in range(m+1):
            temp = float('inf')
            for k in range(i+1):
                temp = min(temp, dp[j+1][k] + ary[j] // (2 ** (i - k)))
                if temp == 0:
                    break
            dp[j][i] = temp

print(dp[0][m])

### FIXED CODE ###

from sys import stdin
import heapq
n, m = map(int, stdin.readline().rstrip().split())
ary = list(map(int, stdin.readline().rstrip().split()))

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


heapq._heapify_max(ary)

for i in range(m):
    temp = _heappop_max(ary) // 2
    _heappush_max(ary, temp)

res = sum([heapq.heappop(ary) for _ in range(n)])
print(res)
### BUGGY CODE ###

s=[s for s in input()]
q=int(input())
for _ in range(q):
  a=list(input().split())
  if a[0]=='1':s=s[::-1]
  else:
    if a[1]=='1':s=[a[2]]+s
    else:s+=[a[2]]
print(''.join(s))

### FIXED CODE ###

s=input()
q=int(input())
flag=0
t=['' for _ in range(2)]
cnt=0
for _ in range(q):
  a=list(input().split())
  if a[0]=='1':
    flag=1-flag
    cnt+=1
  else:
    if a[1]=='1':t[flag]+=a[2]
    else:t[1-flag]+=a[2]
ans=t[0][::-1]+s+t[1]
if cnt%2:ans=ans[::-1]
print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())
min_mod = 2019
flg=[0]*2018
for i in range(L,R):
    idx=i%2019
    if flg[idx]==0:
        for j in range(i+1,R+1):
            mod  = (i*j)%2019
            if min_mod > mod:
                min_mod=mod
        flg[idx]=1
print(min_mod)

### FIXED CODE ###

L, R = map(int, input().split())
min_mod = 2019
flg=[0]*2019
flg2=[0]*2019
for i in range(L,R):
    idx=i%2019
    if flg[idx]==1:
        break
    if flg[idx]==0:
        for j in range(i+1,R+1):
            mod  = (i*j)%2019
            if flg2[mod]==1:
                break
            flg2[mod]=1
            if min_mod > mod:
                min_mod=mod
        flg[idx]=1
print(min_mod)
### BUGGY CODE ###

import fractions

N,M = map(int, input().split())
A = [int(a) for a in input().split()]

for i in range(N):
    A[i] //= 2
    
num = 1
for i in range(N):
    num = num*A[i]//fractions.gcd(num, A[i])
    
f = 0
for i in range(N):
    if (num//A[i])%2 == 0:
        f = 1
        break
        
if f == 0 and M >= num:
    ans = 1
    M -= num
    ans += M//(2*num)
    print(ans)
else:
    print(0)

### FIXED CODE ###

import fractions

N,M = map(int, input().split())
A = [int(a) for a in input().split()]

for i in range(N):
    A[i] //= 2
    
num = 1
f = 0
for i in range(N):
    num = num*A[i]//fractions.gcd(num, A[i])
    if num > M:
        f = 1
        break
    
for i in range(N):
    if (num//A[i])%2 == 0:
        f = 1
        break
        
if f == 0 and M >= num:
    ans = 1
    M -= num
    ans += M//(2*num)
    print(ans)
else:
    print(0)
### BUGGY CODE ###

from itertools import combinations

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for x, y, z in list(combinations(L, 3)):
    if x + y > z:
        answer += 1
print(answer)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect_left(L[j+1:], L[i]+L[j])
print(answer)
### BUGGY CODE ###

import copy
N,K=list(map(int,input().split()))
a=list(map(int,input().split()))

num=0
a_sum=[0]
for i in range(N):
  num+=a[i]
  a_sum.append(num)
  

a_mat=[[0 for i in range(N)] for j in range(N)]
non_zero=[]
for i in range(N):
  for j in range(i,N):
    a_mat[i][j] = a_sum[j+1]-a_sum[i]
    non_zero.append([i,j])

a_mat2=copy.deepcopy(a_mat)

maxbit=1
while True:
  if a_sum[N]<2**maxbit and a_sum[N]>=2**(maxbit-1): 
    break
  else:
    maxbit+=1
maxnum=0
num_rest=int(N*(N+1)/2)
num_rest_now=int(N*(N+1)/2)
for bit in range(maxbit):
  non_zero2=[]
  for i, j in non_zero:
    if a_mat[i][j]&(2**(maxbit-bit-1)) == 0 and a_mat[i][j]!=0:
      num_rest_now-=1
      a_mat2[i][j]=0
    else:
      non_zero2.append([i,j])
  #print(non_zero)
  #print(a_mat)
  #print(num_rest_now)
  
  if num_rest_now >= K:
    maxnum+=2**(maxbit-bit-1)
    a_mat=copy.deepcopy(a_mat2)
    num_rest=num_rest_now
    non_zero=copy.deepcopy(non_zero2)
  else:
    a_mat2=copy.deepcopy(a_mat)
    num_rest_now=num_rest
    
  
  
print(maxnum)
    

### FIXED CODE ###

import sys
from collections import deque, defaultdict
import copy
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

N, K = list(map(int, input().split()))
a = list(map(int, input().split()))
sum_a = [0, a[0]]
for i in range(1, N):
    sum_a.append(sum_a[-1]+a[i])

bubunwa = []
for i in range(N):
    for j in range(i + 1, N + 1):
        bubunwa.append(sum_a[j] - sum_a[i])

max_bit = 2
while True:
    if sum_a[-1] < 2**max_bit:
        break
    max_bit += 1

sum = 0
for i in range(max_bit ,-1, -1):
    kouho = []
    for n in bubunwa:
        if n & 2**i == 2**i:
            kouho.append(n)
    if len(kouho) >= K:
        bubunwa = copy.deepcopy(kouho)
        sum += 2**i

print(sum)
### BUGGY CODE ###


Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    LR.append(list(map(int,input().split())))
    l,r=LR[-1]
    L=l if l>L else L
    R=r if r>R else R

M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=set()
a=2
count=0
for a in range(2,M):
    if a in numlst:
        numlst.remove(a)
        if a:
            sosuulst.add(a)
        numLst=list(numlst)
        for i in numLst:
            if i%a==0:
                numlst.remove(i)
        if (a+1)//2 in sosuulst:
            count+=1
    if a>=3:
        lst[a]=count
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])


### FIXED CODE ###


Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
# ab.sort(key=lambda tup:(tup[0],tup[1]))
visited=[0]*(n+1)
cnt=[0]*(n+1)
data=[[] for i in range(n+1)]

for i in ab:
	data[i[0]].append(i[1])
	data[i[1]].append(i[0])
for j in px:
	cnt[j[0]]+=j[1]
	# print(cnt)
# count=0
def plus(now,value,parent):
	for i in data[now]:
		# global count
		# count+=1
		if i==parent:continue
			
		cnt[i]+=value
		visited[i]=1
		# print(cnt)	
		
		plus(i,cnt[i],now)
		
		
visited[1]=1
plus(1,cnt[1],0)
print(*cnt[1:])
# print(count)

# ans=sorted(cnt.items())
# print(*[i[1] for i in ans])



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
# ab.sort(key=lambda tup:(tup[0],tup[1]))
visited=[0]*(n+1)
cnt=[0]*(n+1)
data=[[] for i in range(n+1)]

for i in ab:
	data[i[0]].append(i[1])
	data[i[1]].append(i[0])
for j in px:
	cnt[j[0]]+=j[1]
	# print(cnt)
# count=0
def plus(now,value,parent):
	for i in data[now]:
		# global count
		# count+=1
		if i==parent:continue
			
		cnt[i]+=value
		visited[i]=1
		# print(cnt)	
		
		plus(i,cnt[i],now)
		
		
visited[1]=1
plus(1,cnt[1],0)
print(*cnt[1:])
# print(count)

# ans=sorted(cnt.items())
# print(*[i[1] for i in ans])
### BUGGY CODE ###

import collections
N = input()
inp = map(int, input().split())
dic = dict(collections.Counter(inp))
wa = 0
for i in range(len(dic)):
    wa += list(dic.keys())[i] * list(dic.values())[i]
for i in range(int(input())):
    a, b = map(int, input().split())
    se = set(dic.keys())
    if a in se:
        wa += dic[a] * (b-a)
        if b in se:
            pass
        else:
            dic[b] = 0
        dic[b] += dic[a]
        dic[a] = 0
    print(wa)

### FIXED CODE ###

import collections
N = int(input())
inp = list(map(int,input().split()))
dic = dict(collections.Counter(inp))
wa = 0
for i, j in dic.items():
	wa += i * j
se = set(dic.keys())
for i in range(int(input())):
	a, b = map(int,input().split())
	if a in se:
		wa += dic[a] * (b-a)
		if b in se:
			pass
		else:
			dic[b] = 0
		se.add(b)
		dic[b] += dic[a]
		dic[a] = 0
	print(wa)
### BUGGY CODE ###

N,Q=map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PQ = [list(map(int,input().split())) for _ in range(Q)]
AB.sort()
PQ.sort()
l=[[] for _ in range(N)]
ans=[0]*N
for a,b in reversed(AB):
	l[a-1].append(b)
	l[a-1].extend(l[b-1])
for p,q in PQ:
	ans[p-1]+=q
	for i in l[p-1]:
		ans[i-1]+=q
print(*ans)

### FIXED CODE ###


N,Q=map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PQ = [list(map(int,input().split())) for _ in range(Q)]
#AB.sort()
#PQ.sort()
l=[[] for _ in range(N)]
ans=[0]*N
for a,b in AB:
	l[a-1].append(b-1)
for p,q in PQ:
	ans[p-1]+=q
for i in range(N-1):
	for j in l[i]:
		ans[j]+=ans[i]
	
print(*ans)
### BUGGY CODE ###



n, k = [0] * 2
a = []

def format_input(filename = None):
	global n, k
	global a
	if filename == None:
		n, k = list(map(int, input().split()))
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**5)
		k = rng(1, 10**18)
		a = [rng(1, n) for i in range(n)]
		print(n, k)
		print(' '.join(list(map(str, a))))

def get_answer():
	loop = [1]
	start = -1
	while start == -1:
		node = a[loop[-1]-1]
		if loop.count(node) > 0:
			start = loop.index(node)
		else:
			loop.append(node)

	l = len(loop)
	if k >= l:
		answer = loop[(k - l) % (l - start) + start]
	else:
		answer = loop[k]

	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)


### FIXED CODE ###

from collections import defaultdict

n, k = [0] * 2
a = []

def format_input(filename = None):
	global n, k
	global a
	if filename == None:
		n, k = list(map(int, input().split()))
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**5)
		k = rng(1, 10**18)
		a = [rng(1, n) for i in range(n)]
		print(n, k)
		print(' '.join(list(map(str, a))))

def get_answer():
	loop = [1]
	loop_index = defaultdict(int)
	start = -1
	while start == -1 and len(loop) < k + 1:
		node = a[loop[-1]-1]
		if loop_index[node] > 0:
			start = loop_index[node]
		elif node == 1:
			start = 0
		else:
			loop.append(node)
			loop_index[node] = len(loop) - 1

	l = len(loop)
	if k >= l:
		answer = loop[(k - l) % (l - start) + start]
	else:
		answer = loop[k]

	return answer

if __name__ == '__main__':
	format_input()

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

x=input().split()

flag=0

for K in range(0,1000000000):
    a=(int(x[0])-K)*(int(x[0])-K)
    b=(int(x[1])-K)*(int(x[1])-K)
    
    if a==b:
        print(K)
        flag=+1

if flag==0:
    print('IMPOSSIBLE')

### FIXED CODE ###

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

if (A-B)%2==0:
    print(int((A+B)/2))
else :
    print('IMPOSSIBLE')
### BUGGY CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]
ans = []
count = collections.Counter(a)
for i in range(q):
  total = 0
  num = count[bc[i][0]]
  count[bc[i][0]] = 0
  count[bc[i][1]] += num
  for key, value in zip(count.keys(), count.values()):
    total += int(key) * int(value)
  ans.append(total)

for out in ans:
  print(out)

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]
ans_count = []
total = 0
for i in range(n):
  total += a[i]

count = collections.Counter(a)
for i in range(q):
  num = count[bc[i][0]]
  count[bc[i][0]] = 0
  count[bc[i][1]] += num
  total += (bc[i][1] - bc[i][0]) * num
  print(total)
### BUGGY CODE ###

import numpy as np
N,M,Q=map(int, input().split())

left=[]
right=[]
for i in range(M):
    l,r=map(int, input().split())
    left.append(l)
    right.append(r)
left=np.array(left)
right=np.array(right)
for i in range(Q):
    p,q=map(int, input().split())
    l=left>=p
    r=right<=q
    ans=(l*r).sum()
    print(ans)

### FIXED CODE ###

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

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

#print(L)

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

s=input()

max_len=0
for i in range(1,len(s)):
  tmp=""
  arr=[s[:i]]
  for s_ in s[i:]:
    tmp+=s_
    if tmp != arr[-1]:
      arr.append(tmp)
      tmp=''
  max_len=max(max_len,len(arr))
print(max_len)

### FIXED CODE ###

s=input()

max_len=0
tmp=""

for i in range(1,min(len(s)+1,3)):
  last=s[:i]
  cnt=1
  for s_ in s[i:]:
    tmp+=s_
    if tmp != last:
      last=tmp
      tmp=''
      cnt+=1
  max_len=max(max_len,cnt)

print(max_len)
### BUGGY CODE ###

x=input().split()

y=[0]*2

y[0]=int(x[0])
y[1]=int(x[1])

K=0

while 1:
    if y[0]+y[1]==2*K:
        print(K)
        
    K=+1
    
    if y[1]<=K:
        print('IMPOSSIBLE')
        break;

### FIXED CODE ###

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

if (A-B)%2==0:
    print(int((A+B)/2))
else :
    print('IMPOSSIBLE')
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
count = 0
for i in range(n):
    for j in range(n):
        if i != j and a[i] % a[j] == 0:
            break
    else:
        count += 1
print(count)


### FIXED CODE ###

def func(n, a):
    mx = max(a)
    x = [0] * (mx + 1) # len(x)
    for i in a:
        x[i] += 1
    for i in range(1, mx + 1):
        if x[i] != 0:
            for j in range(2 * i, mx + 1, i):
                x[j] = 0
        if x[i] > 1:
            x[i] = 0
    print(sum(x)) # 31401

n = int(input())
a = list(map(int, input().split()))
func(n, a)
### BUGGY CODE ###

# import numpy as np
# import scipy as sp
# import sys
# input = sys.stdin.readline
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=list(map(int, input().split()))  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# a=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# a=[int(input()) for _ in range (n)]  #リスト入力  改行でa1 ... anのとき
# s=[list(map(str,list(input()))) for i in range(h)]  # 文字列の二次元配列入力
# s = [list(map(int, input().split())) for i in range(n)] # 数値の二次元配列入力
# a = b[:], a = [x[:] for x in b] # deepcopy
# chr(ord('a') + 1) # chrのインクリメント
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）

n, w = list(map(int, input().split()))
wl = [0] * n
vl = [0] * n
for i in range(n):
    wl[i], vl[i] = map(int, input().split())


dp = [[0]*(w+1)for _ in range(n+1)]  # h:item w:weight v:value
for i in range(n):
    for j in range(w+1):
        if j+wl[i] <= w:
            dp[i+1][j+wl[i]] = max(dp[i+1][j+wl[i]], dp[i][j]+vl[i])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[-1][-1])


### FIXED CODE ###

n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

dp = [[0]*(w+1) for _ in range(n+1)]

for sum_w in range(w+1):
    for i in range(1, n+1):
        if ws[i-1] <= sum_w:
            dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-ws[i-1]]+v[i-1])
        else:
            dp[i][sum_w] = dp[i-1][sum_w]

print(dp[-1][-1])
### BUGGY CODE ###

N = int(input())
S = input()

res = 0
for i in range(N):
  for j in range(i+1, N):
    for k in range(j+1, N):
      if (j-i) != (k-j):
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
          res += 1

print(res)

### FIXED CODE ###

N = int(input())
S = input()

r, g, b = 0, 0, 0
for c in S:
  if c == "R": r += 1
  if c == "G": g += 1
  if c == "B": b += 1

total = r*g*b

for i in range(N):
  for j in range(i+1, N):
    if S[i] == S[j]: continue

    k = 2*j - i
    if k >= N: continue
    if S[i] == S[k] or S[j] == S[k]: continue
    total -= 1

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

N = int(input())
a = list(map(int, input().split()))
ans = 0
i = 1
j = 0
while j < N:
    if i not in a[j:]:
        ans += N - j
        break
    nj = a[j:].index(i)
    ans += nj - j
    i += 1
    j = nj + 1
if i == 1:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 0
x = 1
for i in a:
    if i == x:
        x += 1
    else:
        ans += 1
if x == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import networkx as nx

path = nx.Graph()
room_num, path_num = map(int, input().split())
for i in range(1, room_num):
	path.add_node(i)
for _ in range(path_num):
    a, b = map(int, input().split())
    path.add_edge(a, b)
if nx.is_connected(path):
    print("Yes")
    ans = []
    for n in range(2, room_num+1):
        preans = nx.shortest_path(path, target=1)
    for n in range(2, room_num+1):
    	print(preans[n][1])
else:
    print("No")

### FIXED CODE ###


from collections import deque

room_num, path_num = map(int, input().split(" "))
graph = [[] for _ in range(room_num)]
dis = [-1] * room_num
count = [0] * room_num
count[0] = 1
for _ in range(path_num):
    a, b = map(int, input().split(" "))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
dis[0] = 0
q = deque()
q.append(0)
while q:
    pop = q.popleft()
    for n in graph[pop]:
        if count[n] ==1:
            continue
        else:
            count[n] = 1
            dis[n] = pop+1
            q.append(n)
if sum(dis) == room_num:
    print("No")
else:
    del dis[0]
    print("Yes")
    for s in dis:
        print(s)
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

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

susicount = [0,0,0]
for a in A:
  susicount[a-1] += 1
#print(susicount)

# dp[i][j][k]:寿司3個のお皿がi枚、2個のがj枚、1個がk枚のときの期待値
# dp[i][j][k] = i/N * dp[i-1][j+1][k]
#             + j/N * dp[i][j-1][k+1]
#             + k/N * dp[i][j][k-1]
#             + (N-i-j-k)/N * dp[i][j][k]
#             + 1
# dp[i][j][k]を移項すると、
# dp[i][j][k] = 1/(i+j+k) * (i * dp[i-1][j+1][k]
#                          + j * dp[i][j-1][k+1]
#                          + k * dp[i][j][k-1]
#                          + N)
dp = [[[-1 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]

def rec(i,j,k):
  if i == 0 and j == 0 and k == 0:
    return 0
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 0
  if i != 0:
    res += i * rec(i-1,j+1,k)
  if j != 0:
    res += j * rec(i,j-1,k+1)
  if k != 0:
    res += k * rec(i,j,k-1)
  res = (res+N)/(i+j+k)
  dp[i][j][k] = res
  return dp[i][j][k]

print(rec(susicount[2],susicount[1],susicount[0]))

### FIXED CODE ###

# 再帰関数を使うとTLEになるので、3重ループにしてみる。
from collections import defaultdict

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

sushi = [0,0,0]
for a in A:
  sushi[a-1] += 1

# dp[i][j][k]:寿司3個のお皿がi枚、2個のがj枚、1個がk枚のときの期待値
# dp[i][j][k] = i/N * dp[i-1][j+1][k]
#             + j/N * dp[i][j-1][k+1]
#             + k/N * dp[i][j][k-1]
#             + (N-i-j-k)/N * dp[i][j][k]
#             + 1
# dp[i][j][k]を移項すると、
# dp[i][j][k] = 1/(i+j+k) * (i * dp[i-1][j+1][k]
#                          + j * dp[i][j-1][k+1]
#                          + k * dp[i][j][k-1]
#                          + N)
dp = [[[0.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)] # 型推論で時間がかからないように0ではなく0.0とする。

for i in range(N+1):
  for j in range(N+1):
    for k in range(N+1):
      if i+j+k > N or i+j+k == 0:
        continue
      if i>0:
        dp[i][j][k] += i * dp[i-1][j+1][k]
      if j>0:
        dp[i][j][k] += j * dp[i][j-1][k+1]
      if k>0:
        dp[i][j][k] += k * dp[i][j][k-1]
      dp[i][j][k] += N
      dp[i][j][k] /= (i+j+k)

print(dp[sushi[2]][sushi[1]][sushi[0]])