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


def BinarySearchLowerBound(_arr, _ele): # arr is strictly increasing
    low_ind = 0
    up_ind = len(_arr) - 1
    if _arr[low_ind] >= _ele:
        return low_ind
    if _arr[up_ind] <= _ele:
        return up_ind + 1
    found = None
    while (up_ind - low_ind) > 1:
        mid = (up_ind + low_ind) / 2
        if _arr[mid] < _ele:
            low_ind = mid
        elif _arr[mid] > _ele:
            up_ind = mid
        elif _arr[mid] == _ele:
            found = mid
            break
    if found is not None:
        cnt = found
    else:
        cnt = up_ind
    return cnt

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        if len(D) == 0:
            break
        it = BinarySearchLowerBound(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            D.pop(it)
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[D[lit][1]] = Xi
                l[lit] = rit
                lit += 1
    for i in range(Q):
        print ans[i]

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

N = int(input())
Ss = input().replace(" ", '')
part = ""
for n, i in enumerate(Ss):
	if n != 0:
		if i == part[0]:
			Ss_cp = Ss[::1]
			Ss_cp = Ss_cp.replace(part, '')
			if Ss_cp == '':
				print(N//len(part))
				exit()
	part += Ss[n]
else:
	print(1)


### FIXED CODE ###

N = int(input())
Ss = input().split()
res = 1
for t in range(1, N+1):
	if (N%t != 0): continue
	f = False
	for i in range(N-t):
		if (Ss[i] == Ss[i + t]): continue
		f = True
		break
	if (f): continue
	res = N // t
	break

print(res)
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
c=0
for i in range(N):
  m=min(P[:i+1])
  if P[i]==m:
    c+=1
    
print(c)

### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
c=0
m=max(P)
for i in range(N):
  m=min(m,P[i])
  if P[i]==m:
    c+=1
    
print(c)
### BUGGY CODE ###

_ = int(input())
members = input()

counts = []
for i in range(len(members)):
    count=0
    for j in range(len(members)):
        if i == j:
            continue
        else:
            if (members[j] == 'W' and i<j) or (members[j] == 'E' and i>j):
                continue
            else:
                count+=1
    counts.append(count)
print(min(counts))

### FIXED CODE ###

n = int(input())
members = input()
m_e = members.count("E")
cost = m_e
costs = []
for i in range(n):
    if members[i]=="E":
        cost-=1
    if (i!=0 and members[i-1]=="W"):
        cost+=1
    costs.append(cost)
print(min(costs))
### BUGGY CODE ###

n = int(input())
h = list(map(lambda x: int(x), input().split(" ")))

ans = 0

for i in range(0,n):
	kari = 0
	j = i
	while j<n-1 and h[j] >= h[j+1]:
		kari += 1
		j += 1
	if ans < kari:
		ans = kari
	if ans-1 >= n-i:
		break

print(ans)

### FIXED CODE ###

n = int(input())
h = list(map(lambda x: int(x), input().split(" ")))

ans = 0

kari = 0
i = 0
for m in range(0,n-1):
	if h[m] >= h[m+1]:
		kari += 1
	else:
		kari = 0
	if ans < kari:
		ans = kari



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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug
from functools import lru_cache

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

def mutual_division_method(a, b):
    while not (a == 0 or b == 0):
        if a < b:
            b = b % a
        else:
            a = a % b
    if a == 0:
        return b
    else:
        return a



def gcd(a, b, c):
    #print('a, b, c', a, b, c) # debug
    d = mutual_division_method(a, b)
    e = mutual_division_method(d, c)
    #print('e', e) # debug
    return e

if __name__ == '__main__':
    k = int(input())
    s = 0
    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                l = a, b, c
                sorted(l)
                ans = gcd(*l)
                s += ans
    #print('s') # debug
    print(s)

    #print('\33[32m' + 'end' + '\033[0m') # debug


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug
from functools import lru_cache

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

def mutual_division_method(a, b):
    while not (a == 0 or b == 0):
        if a < b:
            b = b % a
        else:
            a = a % b
    if a == 0:
        return b
    else:
        return a



def gcd(a, b, c):
    #print('a, b, c', a, b, c) # debug
    d = mutual_division_method(a, b)
    e = mutual_division_method(d, c)
    #print('e', e) # debug
    return e

if __name__ == '__main__':
    k = int(input())
    s = 0
    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                ans = gcd(a, b, c)
                s += ans
    #print('s') # debug
    print(s)

    #print('\33[32m' + 'end' + '\033[0m') # debug
### BUGGY CODE ###

import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.8:
        return # gori~~~
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')

### FIXED CODE ###

import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,sys.stdin.readline().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.8:
        # gori~~~
        print('No')
        exit()
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')
### BUGGY CODE ###

import numpy as np
N = int(input())
trial = 10**8
arr = np.random.randint(1,N+1,trial)
x = np.count_nonzero(arr&1)
print(x/trial)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())

odd = (N+1)//2
print(odd/N)
### BUGGY CODE ###

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

Dices = list(map(lambda n:(n+1)/2,Dices))

# from collections import deque

# d=deque([])
# total= 0
# for i in range(N):
#     d.append((Dices[i]+1)/2)
#     if len(d)==K:
#         total = max(total,sum(d))
#         d.popleft()

# print(total)

#累積和
S=[0]*(N+1)
total = 0

for i in range(N+1):
    S[i] = sum(Dices[:i])

for j in range(N-K+1):
    total = max(total,S[j+K]-S[j])


print(total)

### FIXED CODE ###

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

Dices = list(map(lambda n:(n+1)/2,Dices))
import numpy as np 
Dices = np.cumsum(Dices)
# from collections import deque

# d=deque([])
# total= 0
# for i in range(N):
#     d.append((Dices[i]+1)/2)
#     if len(d)==K:
#         total = max(total,sum(d))
#         d.popleft()

# print(total)

#累積和
S=np.append(0,Dices)
total = 0
# for i in range(N+1):
#     S[i] = sum(Dices[:i])

for j in range(N-K+1):
    total = max(total,S[j+K]-S[j])

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

import sys

inf = sys.maxsize
N, K = map(int, input().split())
heights = list(map(int, input().split()))

dp = [inf]*N
dp[0] = 0


def chmin(a, b, diff):
    if dp[a] > dp[b] + diff:
        dp[a] = dp[b] + diff
    return


for i in range(N):
    for j in range(1, K+1):
        if i-j >= 0:
            chmin(i, i-j, abs(heights[i]-heights[i-j]))

print(dp[N-1])

### FIXED CODE ###

import sys

inf = sys.maxsize
N, K = map(int, input().split())
heights = list(map(int, input().split()))

dp = [inf]*N
dp[0] = 0


def chmin(a, b, diff):
    if dp[a] > dp[b] + diff:
        dp[a] = dp[b] + diff
    return


for i in range(N):
    for j in range(1, K+1):
        if i-j >= 0:
            chmin(i, i-j, abs(heights[i]-heights[i-j]))

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

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

cnt = 1
after = []
for i in range(1, N):
    after.append(P[i-1])
    if min(after) >= P[i]:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 1
mini = P[0]
for i in range(1, N):
    if P[i] <= mini:
        mini = P[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

k = int(input())
ans = []
queue = [str(i) for i in range(1,10)]

while queue:
    if len(ans)==k:
        print(ans[k-1])
        break
    now = queue.pop(0)
    ans.append(now)
    t = int(now[-1])
    if t -1 >= 0:
        queue.append(str(now) +str(t-1))

    queue.append(str(now) +str(now)[-1])

    if t +1 <= 9:
        queue.append(str(now) +str(t+1))

### FIXED CODE ###

k = int(input())
ans = [str(i) for i in range(1,10)]
c = 0

while len(ans) < k:
    now = ans[c]
    t = int(now[-1])
    if t != 0:
        ans.append(str(now) +str(t-1))

    ans.append(str(now) +str(now)[-1])

    if t != 9:
        ans.append(str(now) +str(t+1))

    c += 1
print(ans[k-1])
### BUGGY CODE ###

N,K,Q=map(int, input().split())
m=max(N,Q)
A=[0]*m
for i in range(0,Q):
  A[i]=int(input())
S=[0]*m
T=[0]*m
for k in range(Q,m):
  A[k]=-1
  S[k]=-1
  T[k]=-1
  
for i in range(0,N):
  S[i]=A.count(i+1)
  T[i]=Q-S[i]
  if T[i]>=K:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

N,K,Q=map(int, input().split())
A=[0]*Q
for i in range(0,Q):
  A[i]=int(input())

Score_list=[K]*N
Sum_list=[0]*N
for i in range(0,Q):
  Sum_list[A[i]-1]+=1
 
for i in range(0,N):
  if Q-Sum_list[i]>=K:
    print("No")    
  else:
    print("Yes")
### BUGGY CODE ###

from collections import Counter

mod = 10 ** 9 + 7

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

C = Counter()
for a in A:
    if a in C:
        continue

    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
L %= mod

ans = 0
for a in A:
    ans += L * pow(a, mod - 2, mod)
ans %= mod

print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

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

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()
### BUGGY CODE ###

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1

D = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP[t][d][m] = 1
su = 0
D[t][d][m] = 1
for i in range(t, -1, -1):
  for j in range(d + t - i, -1, -1):
    for k in range(N - i - j, -1, -1):
      x = DP[i][j][k]
      y = D[i][j][k]
      if x != 0:
        if i + j + k != 0:
          su += y * N /(i + j + k)
        if i >= 1:
          DP[i - 1][j + 1][k] += x
          D[i - 1][j + 1][k] += y * i / (i + j + k)
        if j >= 1: 
          DP[i][j - 1][k + 1] += x
          D[i][j - 1][k + 1] += y * j / (i + j + k)
        if k >= 1:
          DP[i][j][k - 1] += x
          D[i][j][k - 1] += y * k / (i + j + k)

print(su)


### FIXED CODE ###

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1

D = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
su = 0
D[t][d][m] = 1
for i in range(t, -1, -1):
  for j in range(d + t - i, -1, -1):
    for k in range(N - i - j, -1, -1):
      y = D[i][j][k]
      if i + j + k != 0:
        su += y * N /(i + j + k)
      if i >= 1:
        D[i - 1][j + 1][k] += y * i / (i + j + k)
      if j >= 1: 
        D[i][j - 1][k + 1] += y * j / (i + j + k)
      if k >= 1:
        D[i][j][k - 1] += y * k / (i + j + k)

print(su)
### BUGGY CODE ###

from collections import deque
N=int(input())
S=input()
R=deque()
G=deque()
B=deque()
count=1
for i in S:
    if i=="R":
        R.append(count)
    if i=="G":
        G.append(count)
    if i=="B":
        B.append(count)
    count+=1
ans=0
for j in R:
    for k in G:
        x=len(B)
        if 2*j-k in B:
            x-=1
        if 2*k-j in B:
            x-=1
        if (k+j)/2==(k+j)//2 and (k+j)//2 in B:
            x-=1
        ans+=x
print(ans)


    









        

    









    

        




    















    



    





    






        






    
















        


























            
    


    


    
    














    


    














### FIXED CODE ###

N=int(input())
S=list(input())
S.insert(0,0)
R=S.count("R")
G=S.count("G")
B=S.count("B")
ans=R*G*B
for i in range(1,N-1):
    for j in range(i+1,N):
        k=2*j-i
        if k<N+1 and S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans-=1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
pans = 0
for i in range(n):
    ans = sum(a[i+1:])
    ans *= a[i]
    ans = ans % (10**9+7)
    pans += ans
print(pans%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
pans = 0
sum_ = sum(a)%(10**9+7)
for i in range(n-1):
    sum_ -= a[i]
    ans = sum_ * a[i]
    ans = ans % (10**9+7)
    pans += ans
print(pans%(10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# topological sort
s = []
s.append(0)
parent = [-1]*n
order = []
while s:
    v = s.pop()
    order.append(v)
    for u in g[v]:
        if u == parent[v]:
            continue
        parent[u] = v
        s.append(u)

dp = [1]*n
c = [0]*n
order.reverse()
for v in order:
    dp[v] *= g1[c[v]]
    dp[v] %= mod
    c[v] += 1
    if parent[v] == -1:
        continue
    c[parent[v]] += c[v]
    dp[parent[v]] *= (dp[v]*g2[c[v]])
    dp[parent[v]] %= mod

order.reverse()
ans = [0]*n
for v in order:
    ans[v] = dp[v]
    for u in g[v]:
        if u == parent[v]:
            continue
        dp[u] *= ans[v]*g2[c[v]-1]*g1[c[v]-1-c[u]]*g1[c[u]]*pow(dp[u],(mod-2),mod)
        dp[u] *= g2[c[u]-1]
        dp[u] *= g1[c[v]-1]
        dp[u] *= g2[c[v]-c[u]]
        dp[u] %= mod
        c[u] = c[v]
for i in range(n):
    print(ans[i]%mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# topological sort
s = []
s.append(0)
parent = [-1]*n
order = []
while s:
    v = s.pop()
    order.append(v)
    for u in g[v]:
        if u == parent[v]:
            continue
        parent[u] = v
        s.append(u)

dp = [1]*n
c = [0]*n
order.reverse()
for v in order:
    dp[v] *= g1[c[v]]
    dp[v] %= mod
    c[v] += 1
    if parent[v] == -1:
        continue
    c[parent[v]] += c[v]
    dp[parent[v]] *= (dp[v]*g2[c[v]])
    dp[parent[v]] %= mod

order.reverse()
ans = [0]*n
for v in order:
    ans[v] = dp[v]
    for u in g[v]:
        if u == parent[v]:
            continue
        dp[u] *= ans[v]*g2[c[v]-1]*g1[c[v]-1-c[u]]*g1[c[u]]*pow(dp[u],(mod-2),mod)
        dp[u] *= g2[c[u]-1]
        dp[u] *= g1[c[v]-1]
        dp[u] *= g2[c[v]-c[u]]
        dp[u] %= mod
        c[u] = c[v]
for i in range(n):
    print(ans[i]%mod)
### BUGGY CODE ###

def solve(n, l):
    l.sort()
    r = 0
    for i in range(n - 2):
        li = l[i]
        for j in range(i + 1, n - 1):
            lj = l[j]
            for k in range(j + 1, n):
                if li + lj <= l[k]:
                    break
                else:
                    # print(li, lj, l[k])
                    r += 1
    return r

def main():
    n = int(input())
    l = [int(x) for x in input().split()]
    print(solve(n, l))


main()

### FIXED CODE ###

import bisect

def solve(n, l):
    l.sort()
    r = 0
    for i in range(n - 2):
        li = l[i]
        for j in range(i + 1, n - 1):
            r += bisect.bisect_left(l, li + l[j], j + 1) - j - 1
    return r

def main():
    n = int(input())
    l = [int(x) for x in input().split()]
    print(solve(n, l))


main()
### BUGGY CODE ###

s = input()
k = int(input())

list = {}

for i in range(len(s)):
    for j in range(i + 1,len(s) + 1):
        if(s[i:j] not in list):
            list[s[i:j]] = 0

keys = sorted(list.keys())

print(keys[k - 1])

### FIXED CODE ###

s = input()
k = int(input())

list = {}

for i in range(len(s)):
    for j in range(i + 1,i + 6):
        if(s[i:j] not in list):
            list[s[i:j]] = 0

keys = sorted(list.keys())

print(keys[k - 1])
### BUGGY CODE ###

n = int(input())

def insert(ab, lol) :
    for j in range(len(lol)) :
        if ab[1] > lol[j][1] :
            pass
        else :
            return lol[:j] + [ab] + lol[j:]
    else :
        return lol + [ab]

ablist = []
for i in range(n) :
    ab = list(map(int, input().split()))
    ablist = insert(ab, ablist)
wa = 0
for i in ablist :
    wa += i[0]
    if wa > i[1] :
        print("No")
        break
else :
    print("Yes")

### FIXED CODE ###

from operator import itemgetter

n = int(input())

ablist = [list(map(int, input().split())) for _ in range(n)]
ablist = sorted(ablist, key=itemgetter(1))

wa = 0
for i in ablist :
    wa += i[0]
    if wa > i[1] :
        print("No")
        break
else :
    print("Yes")
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}

for a in A :
    D[a] += 1

dp = [[[0]*(N+1) for j in range(N+1)] for i in range(N+1)]

flag = [[[0]*(N+1) for j in range(N+1)] for i in range(N+1)]

def f(c1, c2, c3) :
    if flag[c1][c2][c3] :
        return dp[c1][c2][c3]
    elif c1 + c2 + c3 == 0 :
        return 0
    else :
        flag[c1][c2][c3] = 1
        res = N / (c1 + c2 + c3)

        if c1 > 0 :
            res += f(c1-1, c2, c3) * (c1 / (c1 + c2 + c3))
        if c2 > 0 :
            res += f(c1+1, c2-1, c3) * (c2 / (c1 + c2 + c3))
        if c3 > 0 :
            res += f(c1, c2+1, c3-1) * (c3 / (c1 + c2 + c3))
        
        dp[c1][c2][c3] = res
        return res

ans = f(D[1], D[2], D[3])

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}
for a in A :
    D[a] += 1

one = D[1]
two = D[2]
three = D[3]

dp = [[[0.0]*(N+1) for j in range(N+1)] for i in range(N+1)]

def f(c1, c2, c3) :
    res = N
    if (c1 > 0) :
        res += dp[c1-1][c2][c3] * c1
    if (c2 > 0) :
        res += dp[c1+1][c2-1][c3] * c2
    if (c3 > 0) :
        res += dp[c1][c2+1][c3-1] * c3
    
    dp[c1][c2][c3] = res/(c1 + c2 + c3)

for k in range(three+1) :
    for j in range(two+three+1 - k) :
        for i in range(one+two+three+1 - (j+k)) :
            if i+j+k == 0 :
                continue
            f(i, j, k)

print(dp[one][two][three])