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

import sys
readline = sys.stdin.readline

MOD = 10**9+7
def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N = int(readline())
height = [0]
H = list(map(int, readline().split()))
height.extend(H)

orih, C = compress(height)

L = len(orih)

dp = [0]*L
dp[0] = 1

phidx = 0
for i in range(1, N+1):
    hidx = C[H[i-1]]
    dp2 = [0]*L
    if phidx >= hidx:
        for h in range(hidx+1):
            dp2[h] = (dp[hidx]+dp[h])%MOD
    else:
        if phidx == 0:
            dp2[0] = pow(2, orih[hidx])
            for h in range(1, hidx+1):
                dp2[h] = pow(2,  orih[hidx]-orih[h]+1, MOD)
        else:
            for h in range(hidx+1):
                dp2[h] = (dp[phidx] + dp[min(phidx, h)])*pow(2, orih[hidx]-orih[max(h, phidx)])%MOD
    dp = dp2[:]
    phidx = hidx
    #print(dp)
print(dp[0])
            


### FIXED CODE ###

import sys
readline = sys.stdin.readline

MOD = 10**9+7
def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N = int(readline())
height = [0]
H = list(map(int, readline().split()))
height.extend(H)

orih, C = compress(height)

L = len(orih)

dp = [0]*L
dp[0] = 1

phidx = 0
for i in range(1, N+1):
    hidx = C[H[i-1]]
    dp2 = [0]*L
    if phidx >= hidx:
        for h in range(hidx+1):
            dp2[h] = (dp[hidx]+dp[h])%MOD
    else:
        if phidx == 0:
            dp2[0] = pow(2, orih[hidx])%MOD
            for h in range(1, hidx+1):
                dp2[h] = pow(2,  orih[hidx]-orih[h]+1, MOD)
        else:
            for h in range(hidx+1):
                dp2[h] = (dp[phidx] + dp[min(phidx, h)])*pow(2, orih[hidx]-orih[max(h, phidx)], MOD)%MOD
    dp = dp2[:]
    phidx = hidx
    #print(dp)
print(dp[0])
### BUGGY CODE ###

import numpy as np
N = int(input())
li = np.array([range(1, N)])
print("{:.0f}".format(np.sum(li)))

### FIXED CODE ###

N = int(input())
print((1 + (N - 1)) * (N - 1) // 2)
### BUGGY CODE ###

#45 ABC135D 桁DP
s=input()
n=len(s)
dp=[[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
	if s[i]=="?":
		c=-1
	else:
		c=int(s[i])
	for j in range(10):
		if c!=-1 and c!=j:
			continue
		for ki in range(13):
			dp[i+1][(ki*10+j)%13]+=dp[i][ki]
	#for j in range(13):
		#dp[i+1][j]%=(10**9+7)
print(dp[n][5]%(10**9+7))

### FIXED CODE ###

#45 ABC135D 桁DP
s=input()
n=len(s)
dp=[[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
	if s[i]=="?":
		c=-1
	else:
		c=int(s[i])
	for j in range(10):
		if c!=-1 and c!=j:
			continue
		for ki in range(13):
			dp[i+1][(ki*10+j)%13]+=dp[i][ki]
	for j in range(13):
		dp[i+1][j]%=(10**9+7)
print(dp[n][5]%(10**9+7))
### BUGGY CODE ###

#coding:utf-8
import math
K=int(input())
result=0
for i in range(1,K+1):
	for j in range(1,K+1):
		for k in range(1,K+1):
			result+=math.gcd(math.gcd(i,j),k)

print(result)

### FIXED CODE ###

#coding:utf-8
from math import*
K=int(input())
result=0
for i in range(1,K+1):
	for j in range(1,K+1):
		for k in range(1,K+1):
			result+=gcd(gcd(i,j),k)

print(result)
### BUGGY CODE ###

n, x, y = input().split()
ans_list = []
for i in range(1, int(n)):
    for j in range(i+1, int(n)+1):
        ans_list.append(min(abs(i-j), abs(i-int(x))+1+abs(j-int(y)), abs(i-int(y))+1+abs(j-int(x))))
for i in range(1, int(n)):
    print(ans_list.count(i))

### FIXED CODE ###

import collections

def distances(n,x,y):
    for i in range(1, int(n)):
        for j in range(i+1, int(n)+1):
            yield min(abs(i-j), abs(i-x)+abs(j-y)+1, abs(i-y)+abs(j-x)+1)

n, x, y = map(int, input().split())

c = collections.Counter(distances(n,x,y))

for i in range(1,n):
    print(c[i])
### BUGGY CODE ###

member, start, round = list(map(int, input().split()))
answer = []
counter = []
for i in range(round):
    answer.append(int(input()))

for i in range(1, member+1):
    counter.append(answer.count(i))

for i in range(member):
    if (start - (round - counter[i])) <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

member, start, round = list(map(int, input().split()))
answer = [0] * (member+1)
for i in range(round):
    answer[int(input())] += 1
for i in range(member):
    if start - (round - answer[i+1]) <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    X, Y, A, B, C = [int(x) for x in input().split()]
    P = [int(x) for x in input().split()]
    Q = [int(x) for x in input().split()]
    R = [int(x) for x in input().split()]

    P.sort(reverse=True)
    Q.sort(reverse=True)
    R.sort(reverse=True)

    xcnt = 0
    ycnt = 0
    rcnt = 0
    ans = 0
    while rcnt < C:
        r = R[rcnt]
        p = float("inf")
        if X - 1 - xcnt >= 0:
            p = P[X - 1 - xcnt]
        q = float("inf")
        if Y - 1 - ycnt >= 0:
            q = Q[Y - 1 - ycnt]
        if p >= r and q >= r:
            break

        if (r - p) > 0 and r - p > r - q:
            xcnt += 1
            rcnt += 1
            ans += r
        elif (r - q) > 0 and r - q > r - p:
            ycnt += 1
            rcnt += 1
            ans += r
    ans += sum(P[:X - xcnt])
    ans += sum(Q[:Y - ycnt])

    print(ans)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    X, Y, A, B, C = [int(x) for x in input().split()]
    P = [int(x) for x in input().split()]
    Q = [int(x) for x in input().split()]
    R = [int(x) for x in input().split()]

    P.sort(reverse=True)
    Q.sort(reverse=True)
    R.sort(reverse=True)

    xcnt = 0
    ycnt = 0
    rcnt = 0
    ans = 0

    for r in R:
        p = float("inf")
        if X - 1 - xcnt >= 0:
            p = P[X - 1 - xcnt]
        q = float("inf")
        if Y - 1 - ycnt >= 0:
            q = Q[Y - 1 - ycnt]
        if p >= r and q >= r:
            break

        if (r - p) > 0 and r - p > r - q:
            xcnt += 1
            rcnt += 1
            ans += r
        else:
            ycnt += 1
            rcnt += 1
            ans += r

    ans += sum(P[:X - xcnt])
    ans += sum(Q[:Y - ycnt])

    print(ans)


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

from collections import deque
S = input()
S  = deque(S)
Q = int(input())

for _ in range(Q):
    string = (input())
    Query = string.replace(' ', '')
    Query = list(Query)

    if Query[0] == "1":
        S = list(S)
        S = S[::-1]
        S= deque(S)
    else:
        if Query[1] == "1":
            S.appendleft(Query[2])
        else:
            S.append(Query[2])

S = list(S)
ans = "".join(S)
print(ans)

### FIXED CODE ###

from collections import deque
S = input()
S  = deque(S)
Q = int(input())

# 0の時は普通、1の時は反転状態
Reverse_Flag = 0  

for _ in range(Q):
    string = (input())
    Query = string.replace(' ', '')
    Query = list(Query)

    if Query[0] == "1":
        if Reverse_Flag == 0:
            Reverse_Flag = 1
        else:
            Reverse_Flag = 0
    
    elif  Query[1] == "1":
        if Reverse_Flag == 0:
            S.appendleft(Query[2])
        else:
            S.append(Query[2])

    else:
        if Reverse_Flag == 0:
            S.append(Query[2])
        else:
            S.appendleft(Query[2])

if Reverse_Flag == 1:
    S = list(S)
    S = S[::-1]
    print("".join(S))
else:
    S = list(S)
    print("".join(S))
### BUGGY CODE ###

#!/usr/bin/env python3
N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
for b in range(-1, 60)[::-1]:
    if b >= 0 and not K >> b & 1:
        continue
    tmp = 0
    for i in range(60)[::-1]:
        c = sum(x >> i & 1 for x in A)
        if i > b:
            tmp += (1 << i) * (N - c if K >> i & 1 else c)
        elif i == b:
            tmp += (1 << i) * c
        else:
            tmp += (1 << i) * max(c, N - c)
    ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
for b in range(-1, 60)[::-1]:
    if b >= 0 and not K >> b & 1:
        continue
    tmp = 0
    for i in range(60)[::-1]:
        c = sum(x >> i & 1 for x in A)
        if i > b:
            tmp += (1 << i) * (N - c if K >> i & 1 else c)
        elif i == b:
            tmp += (1 << i) * c
        else:
            tmp += (1 << i) * max(c, N - c)
    ans = max(ans, tmp)

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

n = int(input())
q = list(map(lambda x:int(x),input().split()))
a = max(q)
b = min(q)
cnt = 0
for d in range(b,a+1):
    ARC = 0
    ABC = 0
    for qq in q:
        if qq >= d : ARC += 1
        else: ABC += 1
    if ARC == ABC:
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
q = list(map(lambda x:int(x),input().split()))
q.sort()
cnt = q[int(n/2)] - q[int(n/2)-1]
print(cnt)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
exist = np.zeros(10**6+1, dtype=int)
exist[A] = 1

if np.gcd.reduce(A) != 1:
    print('not coprime')
elif np.all([exist[i::i].sum() <= 1 for i in range(2, 10**6+1)]):
    print('pairwise coprime')
else:
    print('setwise coprime')

### FIXED CODE ###

from math import gcd

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

g_all = A[0]
for a in A[1:]:
    g_all = gcd(g_all, a)

if g_all > 1:
    print('not coprime')
    quit()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


appeared = [False] * (10**6 + 1)
primes = sieve(10**3)[1]
for a in A:
    if a == 1:
        continue
    for p in primes:
        if a % p == 0:
            if appeared[p]:
                print('setwise coprime')
                quit()
            appeared[p] = True
            while a % p == 0:
                a //= p
    
    if a != 1:
        if appeared[a]:
            print('setwise coprime')
            quit()
        
        appeared[a] = True

print('pairwise coprime')
### BUGGY CODE ###

def is_same(lst):
  n=len(lst)
  for i in range(n-1):
    for j in range(i+1,n):
      if(lst[i]==lst[j]):
        return True
  return False
    

n=int(input())
input_line=[int(x) for x in input().split()]
if(not is_same(input_line)):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

def is_neighbor_same(lst):
  for i in range(len(lst)-1):
    if(lst[i]==lst[i+1]):
      return True
  return False

input()
input_line=[int(x) for x in input().split()]
input_line.sort()
if(is_neighbor_same(input_line)):
  print("NO")
else:
  print("YES")
### BUGGY CODE ###

import itertools
N = int(input())
l = [int(i) for i in input().split()]
count = 0
for v in itertools.combinations(l,3):
    if v[0] < v[1] + v[2]:
        if v[1] < v[0] + v[2]:
            if v[2] < v[1] + v[0]:
                count += 1
print(count)

### FIXED CODE ###

import bisect
N = int(input())
l = [int(i) for i in input().split()]
count = 0
l_new = sorted(l)
for i,a in enumerate(l_new):
    for j,b in enumerate(l_new[i+1:],start = i+1):
        left = bisect.bisect_right(l_new,abs(a-b))
        right = bisect.bisect_left(l_new,a + b)
        count += right - left
        
        if left <= i < right:
            count -= 1
        if left <= j < right:
            count -= 1
        
print(count//3)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
d=[]
for i in range(q):
  l,r=map(int,input().split())
  x=s[l-1:r].replace("AC","1")
  print(x.count("1"))

### FIXED CODE ###

import itertools
n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split())) for i in range(q)]
ans=[0]*(n+1)

for i in range(len(s)-1):
  if s[i]+s[i+1]=="AC":
    ans[i+1]=1
ansr=list(itertools.accumulate(ans))

for i in range(q):
  if ans[lr[i][1]]==1:
    print(ansr[lr[i][1]]-ansr[lr[i][0]-1]-1)
  else:
    print(ansr[lr[i][1]]-ansr[lr[i][0]-1])
### BUGGY CODE ###

import math
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, S = [int(sys.stdin.readline()) for _ in range(2)]


@lru_cache(maxsize=None)
def f(b, n):
    if n < b:
        return n
    return f(b, int(n // b)) + n % b


def bisect_left_callable(fn, x, lo, hi):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


if S > N:
    print(-1)
    exit()
if S == N:
    print(N + 1)
    exit()

# #########
# b = 2
# ans = -1
# prev = 0
# while b <= N:
#     if f(b, N) > prev:
#         print(b, N, f(b, N))
#     prev = f(b, N)
#     b += 1
# ##########

b = 2
ans = -1
while b <= math.sqrt(N) + 1:
    if f(b, N) == S:
        ans = b
        break
    b += 1
if ans >= 0:
    print(ans)
    exit()

for i in range(1, int(math.sqrt(N)) + 1):
    hi = N // i + 1
    lo = N // (i + 1) + 1
    b = bisect_left_callable(lambda x: -f(x, N), -S, lo, hi)
    if f(b, N) == S:
        ans = b
print(ans)



### FIXED CODE ###

import math
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, S = [int(sys.stdin.readline()) for _ in range(2)]


@lru_cache(maxsize=None)
def f(b, n):
    if n < b:
        return n
    return f(b, int(n // b)) + n % b


if S > N:
    print(-1)
    exit()
if S == N:
    print(N + 1)
    exit()

# #########
# b = 2
# ans = -1
# prev = 0
# while b <= N:
#     if f(b, N) > prev:
#         print(b, N, f(b, N))
#     prev = f(b, N)
#     b += 1
# ##########

b = 2
ans = -1
while b <= math.sqrt(N) + 1:
    if f(b, N) == S:
        ans = b
        break
    b += 1
if ans >= 0:
    print(ans)
    exit()

ans = INF
# b > sqrt(N) のとき 2 桁になるので上位桁を全探索する
for d2 in range(1, int(math.sqrt(N)) + 1):
    if (N - S) % d2 == 0:
        b = int(1 + (N - S) // d2)
        if b >= 2 and f(b, N) == S:
            ans = min(ans, b)
if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

S=input()

from collections import defaultdict
d=defaultdict(int)

for i in range(len(S)):
    a=S[i:]
    b=int(a)
    d[b%2019]+=1

ans=0

for k,v in d.items():
    if k==0:
        ans+=v
    else:
        ans+=v*(v-1)//2

print(ans)

### FIXED CODE ###

S=input()

from collections import defaultdict
d=defaultdict(int)

n=len(S)
b=0
for i in range(n):
    a=int(S[n-i-1])
    b+=a*pow(10,i,2019)
    b%=2019
    d[b]+=1

ans=0

for k,v in d.items():
    if k==0:
        ans+=v
    ans+=v*(v-1)//2

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

import sys
def input():
    return sys.stdin.readline()
n, k = list(map(int,input().split(' ')))
path = []
for i in range(n+1):
    path.append([])
for i in range(n-1):
    a, b = list(map(int,input().split(' ')))
    path[a].append(b)
    path[b].append(a)
val = [0] * (n+1)
for i in range(k):
    v, pt = list(map(int,input().split(' ')))
    val[v] += pt

used = {}
q = [1]
used[1] = True
while q:
    v = q.pop(0)
    for next_v in path[v]:
        if next_v not in used:
            used[next_v] = True
            val[next_v] += val[v]
            q.append(next_v)

print(' '.join([str(pt) for pt in val[1:]]))


### FIXED CODE ###

from collections import deque

n, k = list(map(int,input().split(' ')))
path = []
for i in range(n+1):
    path.append([])
for i in range(n-1):
    a, b = list(map(int,input().split(' ')))
    path[a].append(b)
    path[b].append(a)
val = [0] * (n+1)
for i in range(k):
    v, pt = list(map(int,input().split(' ')))
    val[v] += pt

used = {}
q = deque([1])
used[1] = True
while q:
    v = q.pop()
    for next_v in path[v]:
        if next_v not in used:
            used[next_v] = True
            val[next_v] += val[v]
            q.append(next_v)

print(' '.join([str(pt) for pt in val[1:]]))
### BUGGY CODE ###

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

ans = [0] * n
for i in (range(n)):
    ans[i] = a.count(i+1)
    print(ans[i])

### FIXED CODE ###

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

ans = [0] * n
for i in a:
    ans[i-1] += 1

for i in range(n):
    print(ans[i])
### BUGGY CODE ###

from collections import deque
 
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())
 
count = 0
players = set(range(1, n+1))
while True:
    index_lst = []
    for i in players:
        candidate = current[i-1]
        if candidate == 0:
            continue
        if current[candidate-1] == i:
            index_lst += [i, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in set(index_lst):
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    players = index_lst
    count += 1

### FIXED CODE ###

from collections import deque
 
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
players = set(range(1, n+1))
while True:
    index_lst = []
    for i in players:
        candidate = current[i-1]
        if candidate in index_lst:
            continue
        if current[candidate-1] == i:
            index_lst += [i, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in index_lst:
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    players = set(index_lst)
    count += 1
### BUGGY CODE ###

x=int(input())
c=0
while c-x:i=c%120;j=c%217-98;c=i**5-j**5
print(i,j)

### FIXED CODE ###

x=int(input())
[print(i,j)+exit()for i in range(200)for j in range(-i,i)if i**5-j**5==x]
### BUGGY CODE ###

def f(n, m):
    if n < 1 or m < 1:
        return 0
    elif m < W[n - 1]:
        return f(n - 1, m)
    else:
        return max(f(n - 1, m), f(n - 1, m - W[n - 1]) + V[n - 1])


N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
print(f(N, M))


### FIXED CODE ###

N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
# f[n][x] = n番目までの品物でx以上の価値に必要な最小の重さ
f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
a = LI()

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

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

print(rec(a.count(1), a.count(2), a.count(3)))

### FIXED CODE ###

import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (i+j==0) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for i in range(N+1):
            dp[i][E] = 0 if (i+E+k==0) else N/(i+E+k)
        for j in range(E+1):
            for i in range(N+1):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0) and (j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0) and (k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

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

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
s = ns()
d = dict()
for x in 'RGB':
    d[x] = s.count(x)
ans = 0
for i in range(n-1):
    for j in range(i):
        if s[i] != s[j]:
            t = list({'R', 'G', 'B'} - {s[i], s[j]})[0]
            ans += d[t] - ((2*i - j) < n and t == s[2*i - j])
    d[s[i]] -= 1
print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
s = list(map(ord, ns()))
d = dict()
for x in map(ord, list('RGB')):
    d[x] = s.count(x)
tot = sum(map(ord, list('RGB')))
ans = 0
for i in range(n-1):
    for j in range(i):
        if s[i] != s[j]:
            t = tot - s[i] - s[j]
            ans += d[t] - ((2*i - j) < n and t == s[2*i - j])
    d[s[i]] -= 1
print(ans)