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

import numpy as np


H, W = map(int, input().split())

grid = list()
for _ in range(H):
    grid.append(input())

up = np.zeros((H, W), dtype = int)
down = np.zeros((H, W), dtype = int)
left = np.zeros((H, W), dtype = int)
right = np.zeros((H, W), dtype = int)

for col in range(W):
    cnt = 0
    for row in range(H):
        if grid[row][col] == '.':
            cnt += 1
        else:
            cnt = 0
        up[row][col] = cnt
for col in range(W):
    cnt = 0
    for row in reversed(range(H)):
        if grid[row][col] == '.':
            cnt += 1
        else:
            cnt = 0
        down[row][col] = cnt
for row in range(H):
    cnt = 0
    for col in range(W):
        if grid[row][col] == '.':
            cnt += 1
        else:
            cnt = 0
        left[row][col] = cnt
for row in range(H):
    cnt = 0
    for col in reversed(range(W)):
        if grid[row][col] == '.':
            cnt += 1
        else:
            cnt = 0
        right[row][col] = cnt

print(np.max(up + down + left + right) - 3)

### FIXED CODE ###

import numpy as np


H, W = map(int, input().split())
grid = np.array([list(input()) for _ in range(H)]) == "."

up = np.zeros((H, W), dtype = int)
down = np.zeros((H, W), dtype = int)
left = np.zeros((H, W), dtype = int)
right = np.zeros((H, W), dtype = int)

for i in range(H):
    down[i] = (down[i - 1] + 1) * grid[i]
    up[-i - 1] = (up[-i] + 1) * grid[-i - 1]

for i in range(W):
    right[:, i] = (right[:, i - 1] + 1) * grid[:, i]
    left[:, -i - 1] = (left[:, -i] + 1) * grid[:, -i - 1]

print(np.max(up + down + left + right) - 3)
### BUGGY CODE ###

def sums(N):
  res = 0
  for i in range(1, N+1):
    res += i
  return res

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



exp = [0 for _ in range(N)]
for i in range(0, N):
  exp[i] = sums(Ps[i])/Ps[i]

ans = [0 for _ in range(N)]

for i in range(0, K):
  ans[K-1] += exp[i]

for i in range(K, N):
  ans[i] = max(ans[i-1], sum(exp[i+1-K:i+1]))


print(ans[N-1])


### FIXED CODE ###

def sums(N):
  return 1 + (N-1) * 0.5

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

exp = [0 for _ in range(N)]
for i in range(0, N):
  exp[i] = sums(Ps[i])

summed = [0 for _ in range(N)]
summed[0] = exp[0]

for i in range(1, N):
  summed[i] = summed[i-1] + exp[i]

max_i=summed[K-1]

for i in range(K, N):
  max_i = max(max_i, summed[i]-summed[i-K])

print(max_i)
### BUGGY CODE ###

N,T = map(int,input().split())

item=[list(map(int,input().split())) for _ in range(N)]
item = sorted(item,key=lambda x:x[0])

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

for i,(a,b) in  enumerate(item,1):
    for t in reversed(range(T)):
        dist=t+a
        dp[i][dist] = max(dp[i-1][t]+b,dp[i][dist])
        dp[i][t]=max(dp[i-1][t],dp[i-1][t])
ans=0
for l in dp:
    ans=max(ans,max(l))
print(ans)


### FIXED CODE ###

N,T = map(int,input().split())

item=[list(map(int,input().split())) for _ in range(N)]
item = sorted(item,key=lambda x:x[0])

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

for i,(a,b) in  enumerate(item,1):
    for t in reversed(range(T)):
        dist=t+a
        dp[i][dist] = max(dp[i-1][t]+b,dp[i][dist])
        dp[i][t]=max(dp[i-1][t],dp[i-1][t])
ans=0
for l in dp:
    ans=max(ans,max(l))
print(ans)
### BUGGY CODE ###

words = lambda t : list(map(t, input().split()))
n,k = words(int)
xs = words(int)

def divisor (x):
    ans = [1]
    for i in range(2, x//2+1):
        if x % i == 0:
            ans.append(i)
    ans.append(x)
    return list(reversed(ans))

s = sum(xs)
ds = divisor(s)
ans = 1
#print(ds)
for d in ds:
    ms = []
    for x in xs:
        ms.append(x%d)
    ms.sort()
    #print(d,ms)
    f = 0
    f_ttl = ms[f]
    b = len(ms)-1
    b_ttl = d - ms[b]
    while f != b:
        if f_ttl >= b_ttl:
            b -= 1
            b_ttl += d - ms[b]
        else:
            f += 1
            f_ttl += ms[f]
    if k >= f_ttl:
        ans = d
        break
print(ans)


### FIXED CODE ###

words = lambda t : list(map(t, input().split()))
n,k = words(int)
xs = words(int)

def divisor (x):
    ans = []
    for i in range(1, int(x**0.5)+1):
        if x % i == 0:
            ans.append(i)
            if i != x // i:
                ans.append(x//i)
    ans.sort()
    return list(reversed(ans))

s = sum(xs)
#print(s)
ds = divisor(s)
ans = 1
#print(ds)
for d in ds:
    ms = []
    for x in xs:
        ms.append(x%d)
    ms.sort()
    #print(d,ms)
    f = 0
    f_ttl = ms[f]
    b = len(ms)-1
    b_ttl = d - ms[b]
    while f != b:
        if f_ttl >= b_ttl:
            b -= 1
            b_ttl += d - ms[b]
        else:
            f += 1
            f_ttl += ms[f]
    if k >= f_ttl:
        ans = d
        break
print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())
ans = 2019
for i in range(L, R+1):
  for j in range(i+1, R+1):
    ans = min(ans, i * j % 2019)
    if i * j % 2019 == 0:
      break
      break
print(ans)

### FIXED CODE ###

L, R = map(int, input().split())
ans = 2019
for i in range(L, R+1):
  for j in range(i+1, R+1):
    ans = min(ans, i * j % 2019)
    if i * j % 2019 == 0:
      break
  else:
    continue
  break
print(ans)
### BUGGY CODE ###

from numpy import*
n=int(input())
a,b=eval('int64(input().split()),'*2)
c=0
for k in range(28,-1,-1):
    l,h=2**k,2**-~k
    a%=h
    b=sort(b%h)
    m=0
    for t in a:
        i,j=searchsorted(b,l-t),searchsorted(b,h-t)
        if l-t<0:
            i=searchsorted(b,(l-t)%h)-n
        m+=j-i
    c+=m%2*2**k
print(c)

### FIXED CODE ###

def main():
    from numpy import array,searchsorted,sum,hstack
    n,*t=map(int,open(0).read().split())
    a,b=array(t[:n],'i4'),array(t[n:],'i4')
    c=0
    for k in range(28,-1,-1):
        l,h=pow(2,k),pow(2,k+1)
        a%=h
        b%=h
        b.sort()
        y=hstack((b-h,b))
        i=searchsorted(y,l-a)
        j=searchsorted(y,h-a)
        m=sum(j-i)
        c+=m%2*l
    print(c)
if __name__=='__main__':
    main()
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
d=[0]*n
d[0]=0
for i in range(1,n):
    x=l[i]
    d[i]=min([d[j]+abs(x-l[j]) for j in range(max(0,i-k),i)])
print(d[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int, input().split()))
v=[0]*n
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])
### BUGGY CODE ###

s = input()
MOD = 10**9+7
old_dp=[0]*13
new_dp=[0]*13
old_dp[0]=1

for c in s:
    for i in range(13):
        if c == '?':
            for d in range(10):
                new_dp[(10*i+d)%13] += old_dp[i]
        else:
            new_dp[(10*i+int(c))%13] += old_dp[i]
    
    old_dp = [x % MOD for x in new_dp]
    new_dp = [0]*13
print(old_dp[5])

### FIXED CODE ###

s = input()
MOD = 10**9+7
old_dp=[0]*13
new_dp=[0]*13
old_dp[0]=1

for c in s:
    for i in range(13):
        if c == '?':
            for d in range(10):
                new_dp[(10*i+d)%13] += old_dp[i]
        else:
            new_dp[(10*i+int(c))%13] += old_dp[i]
    
    old_dp = [x % MOD for x in new_dp]
    new_dp = [0]*13
print(old_dp[5])
### BUGGY CODE ###

N=int(input())
S=input().split()
list=[]
for i in range(0,N):
  list.append(int(S[i]))
list.sort()
ans=0
for i in range(0,N-2):
  a=list[i]
  tempk=0
  for j in range(i+1,N-1):
    b=list[j]
    flag=0
    for k in range(max(tempk,j+1),N):
      if list[k]>=a+b:
        break
      if k==N-1:
        flag=1
    ans=ans+k-j-1
    if flag==1:
      ans=ans+1
    tempk=k
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int,input().split())))
 
count = 0
for i in range(n):
  for j in range(i+1,n):
    index = bisect.bisect_left(l,l[i]+l[j])
    count += index - j - 1
    
print(count)
### BUGGY CODE ###

from sys import exit
# import copy
# import numpy as np
from collections import deque

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

cnt = 0

a_sum = deque([0])
b_sum = deque([0])
atmp = 0
btmp = 0

for i in a:
    atmp += i
    a_sum.append(atmp)

for i in b:
    btmp += i
    b_sum.append(btmp)


for i in range(n+1):
    for j in range(m+1):
        if a_sum[i] + b_sum[j] <= k:
            cnt = max(cnt, i + j)

print(cnt)


### FIXED CODE ###

from sys import exit
import copy
# import numpy as np
from collections import deque

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

cnt = 0


a.insert(0, 0)
b.insert(0, 0)


for i in range(1, n+1):
    a[i] += a[i-1]

for i in range(1, m+1):
    b[i] += b[i-1]

tmp = m
for i in range(n+1):
    for j in range(tmp, -1, -1):
        if a[i] + b[j] <= k:
            cnt = max(cnt, i + j)
            tmp = j
            break


print(cnt)
### BUGGY CODE ###

# coding: utf-8
# Here your code !
import math
i = input()
count=0

for m in range(int(i)):
    num = int(input())
    arr=[]
    #print(num)
    sq = math.sqrt(num)
    for n in range(1,num):
        if num%n==0:
            arr.append(n)   
    if len(arr)==1:
        count+=1
print(count)

### FIXED CODE ###

# coding: utf-8
# Here your code !
import math
i = input()
count=0

def isPrime(x):
    global count
    if x == 2:
        return True
    if x>2 and x%2==0:
        return False
    i = 3
    while i<=math.sqrt(x):
        if x%i==0:
            return False
        i+=2
    return True

for j in range(int(i)):
    j=int(input())
    if isPrime(j):
        count+=1
print(count)
### BUGGY CODE ###

N = int(input())

a = sorted([int(i) for i in input().split()])
b = sorted([int(i) for i in input().split()])
c = sorted([int(i) for i in input().split()])

import bisect

ans = 0
for i in range(N):
    leftb = bisect.bisect_right(b, a[i])
    for j in range(leftb, N):
        leftc = bisect.bisect_right(c, b[j])
        leftctmp = N - leftc
        ans += leftctmp

print(ans)



### FIXED CODE ###

N = int(input())

a = sorted([int(i) for i in input().split()])
b = sorted([int(i) for i in input().split()])
c = sorted([int(i) for i in input().split()])

import bisect

ans = 0
for i in range(N):
    lefta = bisect.bisect_left(a, b[i])
    leftc = N - bisect.bisect_right(c, b[i])

    ans += lefta * leftc

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

import math

k = int(input())
k_range = range(1, k + 1)

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


sum_gcd = 0
for l in k_range:
    for m in k_range:
        for n in k_range:
            sum_gcd += math.gcd(n, math.gcd(l, m))

print(sum_gcd)

### FIXED CODE ###

import math

k = int(input())
k_range = range(1, k + 1)

sum_gcd = 0
for l in k_range:
    temp = 0
    for m in k_range:
        temp = math.gcd(l, m)
        for n in k_range:
            sum_gcd += math.gcd(n, temp)

print(sum_gcd)
### BUGGY CODE ###

def main():
    h, w = map(int, input().split())

    field = [input() for _ in range(h)]

    points = [[0 for _ in range(w)] for _ in range(h)]

    for i in range(h):
        left = 0
        for j in range(w):
            if field[i][j] == '#':
                for k in range(left, j):
                    points[i][k] += j-left
                left = j+1
                continue
        for k in range(left, w):
            points[i][k] += w-left

    #print("\n".join(str(point) for point in points))
    for j in range(w):
        up = 0
        for i in range(h):
            if field[i][j] == '#':
                for k in range(up, i):
                    points[k][j] += i-up
                up = i+1
                continue
        for k in range(up, h):
            points[k][j] += h-up

    psoudo_ans = max(max(line) for line in points)
    print(max(0, psoudo_ans-1))
    #print("\n".join(str(point) for point in points))


main()

### FIXED CODE ###

def main():
    h, w = map(int, input().split())

    field = [input() for _ in range(h)]

    points = [[0 for _ in range(w)] for _ in range(h)]

    for i in range(h):
        left = 0
        for j in range(w):
            if field[i][j] == '#':
                for k in range(left, j):
                    points[i][k] += j-left
                left = j+1
                continue
        for k in range(left, w):
            points[i][k] += w-left

    #print("\n".join(str(point) for point in points))
    for j in range(w):
        up = 0
        for i in range(h):
            if field[i][j] == '#':
                for k in range(up, i):
                    points[k][j] += i-up
                up = i+1
                continue
        for k in range(up, h):
            points[k][j] += h-up

    psoudo_ans = max(max(line) for line in points)
    print(max(0, psoudo_ans-1))
    #print("\n".join(str(point) for point in points))


main()
### BUGGY CODE ###

from collections import defaultdict,deque
n,m,k=map(int,input().split())
F=defaultdict(set)
B=defaultdict(set)
for i in range(m):
   a,b=map(int,input().split())
   F[a].add(b)
   F[b].add(a)
for i in range(k):
   c,d=map(int,input().split())
   B[c].add(d)
   B[d].add(c)

ans=[0]*n
for i in F:
   V=[]
   for j in F[i]:
      que=deque([j])
      while que:
         s=que.pop()
         if s not in V:
            V.append(s)
            for k in F[s]:
               que.append(k)
   for j in B[i]:
      if j in V:
         V.remove(j)
   ans[i-1]=len(V)-len(F[i])-1
   
print(*ans)      
      

### FIXED CODE ###

import sys
from collections import defaultdict, deque
 
readline = sys.stdin.readline
n, m, k = map(int, readline().split())
# ab = [list(map(int, readline().split())) for i in range(m)]
# cd = [list(map(int, readline().split())) for i in range(k)]
 
friend = [set() for i in range(n)]
not_friend = [set() for i in range(n)]
 
suggest_friends = [-1] * n
for i in range(m):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    friend[a].add(b)
    friend[b].add(a)
    # friend[b].append(a)
for i in range(k):
    c, d = map(int, readline().split())
    c -= 1
    d -= 1
    not_friend[c].add(d)
    not_friend[d].add(c)
    # not_friend[d].append(c)
for i in range(n):
    if suggest_friends[i] != -1:
        continue
    q = deque(friend[i])
    friend_group = set(friend[i])
    while q:
        p = q.popleft()
        for f in friend[p]:
            if not(f in friend_group):
                q.append(f)
                friend_group.add(f)
    num = len(friend_group)
    for f in friend_group:
        suggest_friends[f] = num - 1 - len(friend[f] | not_friend[f] & friend_group)
 
for i in range(n):
    if suggest_friends[i] == -1:
        suggest_friends[i] = 0
print(*suggest_friends)
### BUGGY CODE ###

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

from itertools import combinations

comb = list(combinations([i for i in range(N)],2))

cnt=0
for i in comb:
    if Agents[i[0]] + Agents[i[1]] == abs(i[0] - i[1]):
        cnt+=1

print(cnt)


### FIXED CODE ###

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


##Miss 1
# from itertools import combinations

# comb = list(combinations([i for i in range(N)],2))

# cnt=0
# for i in comb:
#     if Agents[i[0]] + Agents[i[1]] == abs(i[0] - i[1]):
#         print(i[0],i[1])
#         cnt+=1

# print(cnt)

# Miss 2
# for i in range(0,N):
#     k=Agents[i]-(i+1)
#     if k<i:
#         k=i+1
#     for j in range(k,N):
#         if Agents[i]+Agents[j]==abs(i-j):
#             # print(i,j,Agents[i],Agents[j])
#             cnt+=1


L={}
for i in range(N):
    s = i+1 + Agents[i] 
    if s in L:
        L[s]+=1
    else:
        L[s]=1

R={}
for j in range(N):
    s= j+1 - Agents[j]
    if s in R:
        R[s]+=1
    else:
        R[s]=1
cnt=0

for key,value in L.items():
    cnt += R.get(key,0) * value
# for key,value in L.items():
#     for key2,value2 in R.items():
#         if int(key) < int(key2) and value == value2:
#             cnt+=1


print(cnt)
### 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, m = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
ans = list(range(lr[0][0], lr[0][1]+1))
for l, r in lr:
    # print(ans, set(range(l, r+1)))
    ans = list(set(ans) & set(range(l, r+1)))
print(len(ans))


### FIXED CODE ###

import sys
n, m = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
min_gate = 0
max_gate = sys.maxsize
for l, r in lr:
    min_gate = max(min_gate, l)
    max_gate = min(max_gate, r)
print(max(0, max_gate - min_gate + 1))
### BUGGY CODE ###

import math
import itertools


# 素数判定
def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    P = []
    time = 0

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)

    return P

q=int(input())
s= [list(map(int, input().split())) for i in range(q)]
v=eratosthenes(10**5)
w=[0]*(10**5+1)
for i in range(len(v)):
    w[v[i]]+=1

for i in range(10**5,0,-1):
    if w[i]==1:
        if w[(i+1)//2]==1:
            continue
        else:
            w[i]=0
w=list(itertools.accumulate(w))


for i,j in s:
    print(w[j+1] -w[i-1])

### FIXED CODE ###

import itertools
from itertools import accumulate

q=int(input())
x=[list(map(int, input().split())) for i in range(q)]
s=[0]*(1+10**5)
#素数のリスト
n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

primes.sort()
for i in range(len(primes)):
    if primes[i]>5*10**4:
        break
    primes.append(2*primes[i])

primes.sort()
count=0
for i in range(len(primes)-1):
    if primes[i+1]-primes[i]==1 and primes[i+1]%2==0:
        s[primes[i]]=1
s=itertools.accumulate(s)
s=list(s)
a=0
b=0
for i in range(q):
    print(s[x[i][1]]-s[x[i][0]-1])
### BUGGY CODE ###

import math

s = input()
i = int(input())

isR = False
for _ in range(i):
    q = input().split(" ")

    if q[0] == "1":
        isR = not isR
    else:
        if isR:
            if q[1] == "1":
                s = s + q[2]
            else:
                s = q[2] + s
        else:
            if q[1] == "1":
                s = q[2] + s
            else:
                s = s + q[2]

if isR:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

import math

s = input()
i = int(input())

isR = False
head = []
tail = []

for _ in range(i):
    q = input().split(" ")

    if q[0] == "1":
        isR = not isR
    else:
        if isR:
            if q[1] == "1":
                tail.append(q[2])
            else:
                head.append(q[2])
        else:
            if q[1] == "1":
                head.append(q[2])
            else:
                tail.append(q[2])

ans = "".join(head[::-1]) + s + "".join(tail)

if isR:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
*H,=map(int,input().split())

D=[float("inf")]*N
D[0]=0

for i in range(1,N):
  # print(i, "before:",D)
  for k in range(1,K+1):
    if i-k<0:continue
    D[i]=min(D[i], abs(H[i]-H[i-k])+D[i-k])
  # print(i, "after:",D)

print(D[-1])

### FIXED CODE ###

N,K=map(int,input().split())
*H,=map(int,input().split())

D=[float("inf")]*N
D[0]=0
D[1]=abs(H[1]-H[0])
for i in range(2,N):
  # print(i, "before:",D)
  #  print(i,i-1,i-K, max(1, i-K))
  D[i]=min(abs(H[i]-H[k])+D[k] for k in range(max(0,i-K),i))
  # print(i, "after:",D)

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

n = int(input())
Odd = []
OddCount = []
Even = []
EvenCount = []
list = input().split(" ")

for i in range(n):
    if i%2==1:
        x = int(list[i])
        if x in Odd:
            OddCount[Odd.index(x)] += 1
        else:
            OddCount.append(1)
            Odd.append(x)
    else:
        x = int(list[i])
        if x in Even:
            EvenCount[Even.index(x)] += 1
        else:
            EvenCount.append(1)
            Even.append(x)

O1c = max(OddCount)
O1n = Odd[OddCount.index(O1c)]
Odd[OddCount.index(O1c)] = 0
OddCount[OddCount.index(O1c)] = 0

E1c = max(EvenCount)
E1n = Even[EvenCount.index(E1c)]
Even[EvenCount.index(E1c)] = 0
EvenCount[EvenCount.index(E1c)] = 0

if O1c > E1c:
    if O1n != E1n:
        print(n-O1c-E1c)
    else:
        print(n-O1c-max(EvenCount))
elif O1c < E1c:
    if O1n != E1n:
        print(n-O1c-E1c)
    else:
        print(n-max(OddCount)-E1c)
else:
    if O1n == E1n:
        if max(EvenCount) > max(OddCount):
            print(n-O1c-max(EvenCount))
        else:
            print(n-max(OddCount)-E1c)
    else:
        print(n-O1c-E1c)


### FIXED CODE ###

import collections

def answer(list,n):
    Even = collections.Counter(list[::2]).most_common(2)
    Odd = collections.Counter(list[1::2]).most_common(2)

    if Even[0][0] != Odd[0][0]:
        return n - Even[0][1] - Odd[0][1]
    else:
        if len(Even) == 1 or len(Odd) == 1:
            return n // 2
        else:
            return n - max(Even[0][1]+Odd[1][1],Even[1][1]+Odd[0][1])

N = int(input())
list = input().split(" ")
print(answer(list,N))
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
p, q, r = cnt[1], cnt[2], cnt[3]

dp = []
for _ in range(n + 1):
    dp.append([[0] * (r + 1) for _ in range(r + q + 1)])
dp[0][0][0] = 0

for k in range(r + 1):
    for j in range(r + q + 1):
        for i in range(n + 1):
            if i != 0:
                dp[i][j][k] += dp[i - 1][j][k] * i / (i + j + k)
            if (j != 0) and (i != n):
                dp[i][j][k] += dp[i + 1][j - 1][k] * j / (i + j + k)
            if (k != 0) and (j != r + q):
                dp[i][j][k] += dp[i][j + 1][k - 1] * k / (i + j + k)
            if (i + j + k) != 0:
                dp[i][j][k] += n / (i + j + k)

print(dp[p][q][r])


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = [0,0,0]
for x in LI():
    a[x-1] += 1
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(a[2]+1):
    for j in range(a[1]+a[2]+1):
        for i in range(N+1):
            if not (0 < i+j+k <= N): continue
            x = 0.0
            if i > 0: x += dp[i-1][j][k] * (i/N)
            if j > 0: x += dp[i+1][j-1][k] * (j/N)
            if k > 0: x += dp[i][j+1][k-1] * (k/N)
            x += 1.0
            x *= N / (i+j+k)
            dp[i][j][k] = x
print(dp[a[0]][a[1]][a[2]])