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

from collections import deque

if __name__ == '__main__':

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

    ans = [0] * (n+1)

    g = [[i+1, i-1] for i in range(n+1)]
    g[0].clear()
    g[1].pop(1)
    g[n].pop(0)

    g[x].append(y)
    g[y].append(x)

    for i in range(1,n+1):
        q = deque()
        time = 0

        visit = [False] * (n+1)

        q.append((i, time))

        while(len(q) > 0):
            item = q.popleft()

            if visit[item[0]] == False:
                visit[item[0]] = True
                ans[item[1]] += 1
                for k in g[item[0]]:
                    q.append((k, item[1]+1))

    for i in range(1,n):
        print(ans[i]//2)


### FIXED CODE ###

from collections import deque

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

ans = [0] * (n+1)

g = [[i+1, i-1] for i in range(n+1)]
#g[0].clear() pypyにclearなし
g[1].pop(1)
g[n].pop(0)

g[x].append(y)
g[y].append(x)

for i in range(1,n+1):
    q = deque()
    time = 0
    visit = [False] * (n+1)
    q.append((i, time))

    while(len(q) > 0):
        item = q.popleft()

        if visit[item[0]] == False:
            visit[item[0]] = True
            ans[item[1]] += 1
            for k in g[item[0]]:
                q.append((k, item[1]+1))

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

from heapq import *
from collections import defaultdict
INF = float('inf')
class Prim:

    def __init__(self,N):#Nはグラフのノード数
        self.N = N
        self.cost = defaultdict(list)
        self.used = [False for _ in range(N)]
    
    def setcost(self,u,v,w):
        self.cost[u].append((v,w))
        self.cost[v].append((u,w))
    
    def prim(self):
        que = []
        heapify(que)
        used = self.used
        for e in self.cost[0]:
            heappush(que,[e[1],e[0]])
        used[0] = True
        res = 0
        while que:
            p = heappop(que)
            cos,v = p
            if used[v]:continue
            self.used[v] = True
            for e in self.cost[v]:
                if not used[e[0]]:
                    heappush(que,[e[1],e[0]])      
            res += cos
        return res

def main():
    N = int(input())
    cost = []
    for i in range(N):
        x,y = map(int,input().split())
        cost.append((x,y,i))
    prim = Prim(N)
    x = sorted(cost,key=lambda x: x[0])
    y = sorted(cost,key=lambda x: x[1])
    for i in range(N-1):
        a,b,u = x[i]
        c,d,v = x[i+1]
        w = min(abs(a-c),abs(b-d))
        prim.setcost(u,v,w)
        e,f,s = y[i]
        g,h,t = y[i+1]
        u = min(abs(e-g),abs(f-h))
        prim.setcost(s,t,u)
    ans = prim.prim()
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

from heapq import *
from collections import defaultdict
INF = float('inf')
class Prim:

    def __init__(self,N):#Nはグラフのノード数
        self.N = N
        self.cost = defaultdict(list)
        self.used = [False for _ in range(N)]
    
    def setcost(self,u,v,w):
        self.cost[u].append((v,w))
        self.cost[v].append((u,w))
    
    def prim(self):
        que = []
        heapify(que)
        used = self.used
        for e in self.cost[0]:
            heappush(que,[e[1],e[0]])
        used[0] = True
        res = 0
        while que:
            p = heappop(que)
            cos,v = p
            if used[v]:continue
            self.used[v] = True
            for e in self.cost[v]:
                if not used[e[0]]:
                    heappush(que,[e[1],e[0]])      
            res += cos
        return res

def main():
    N = int(input())
    cost = []
    for i in range(N):
        x,y = map(int,input().split())
        cost.append((x,y,i))
    prim = Prim(N)
    x = tuple(sorted(cost,key=lambda x: x[0]))
    y = tuple(sorted(cost,key=lambda x: x[1]))
    for i in range(N-1):
        a,b,u = x[i]
        c,d,v = x[i+1]
        w = min(abs(a-c),abs(b-d))
        prim.setcost(u,v,w)
        e,f,s = y[i]
        g,h,t = y[i+1]
        u = min(abs(e-g),abs(f-h))
        prim.setcost(s,t,u)
    ans = prim.prim()
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import itertools

n = int(input())
list_score = list(map(int, input().split()))
list_score.sort()
ans = 0

for i in range(0, n):
    for j in range(i+1, n):
        for k in range(i+1, j):
            if list_score[k] + list_score[i] > list_score[j]:
                ans += 1

print(ans)

### FIXED CODE ###

from bisect import bisect_left
n = int(input())
list_L = list(map(int, input().split()))
list_L.sort()
ans = 0

for i in range(n):
    for j in range(i+1, n):
        ans += bisect_left(list_L, list_L[i]+list_L[j]) - j - 1

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

n,k=map(int,input().split())
a=list(map(int,input().split()))
c=[n for i in range(n)]
for i in range(k):
    b=[0 for i in range(n)]
    for j in range(n):
        for k in range(max(j-a[j],0),min(j+a[j]+1,n)):
            b[k]+=1
    #print(b)
    a=b
print(*a)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
c=[n for i in range(n)]
for j in range(k):
    d=[0 for i in range(n+1)]
    for i in range(n):
        d[max(i-a[i],0)]+=1
        d[min(i+a[i]+1,n)]-=1
    e=[d[0]]
    for i in range(n-1):#ちょっと特殊な累積和 普通のものの[1:-1]
        e.append(e[i]+d[i+1])
    #print(d,e,sep='\n')
    #print(e)
    a=e
    if e==c:
        break
print(*a)
### BUGGY CODE ###

n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]

ans = 0
d = []
for i in s:
  if i not in d:
    t = s.count(i)
    ans += t*(t-1)//2
    d.append(i)
print(ans)

### FIXED CODE ###

import collections

n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]

c = collections.Counter(s)

ans = 0
for i in set(s):
  x = c[i]
  ans += x * (x -1)//2
print(ans)
### BUGGY CODE ###

class Node:
    def __init__(self, val):
        self.num = val
        self.val = val
        self.is_parent = True
        self.parent = None
        self.childs = []

    def show(self):
        print(self.num, end=" ")
        print(self.is_parent, end=" ")
        for child in self.childs:
            print(child.num, end=" ")

def root(node):
    while node.parent != None:
        node = node.parent
    return node

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

roots = [Node(i) for i in range(N)]
count = N

for i in range(M):
    x, y, z = map(int, input().split())
    x = roots[x-1]
    y = roots[y-1]
    if x.is_parent and y.is_parent:
            y.is_parent = False
            y.parent = x
            count -= 1
            x.childs.append(y)
    else:
        root_x = root(x)
        root_y = root(y)
        if root_x != root_y:
            root_y.is_parent = False
            root_y.parent = root_x
            count -= 1
            root_x.childs.append(root_y)

print(count)

### FIXED CODE ###

class Node:
    def __init__(self, val):
        self.num = val
        self.val = val
        self.is_parent = True
        self.parent = None
        self.childs = []

    def show(self):
        print(self.num, end=" ")
        print(self.is_parent, end=" ")
        for child in self.childs:
            print(child.num, end=" ")

def root(node):
    depth = 0
    while node.parent != None:
        node = node.parent
        depth += 1
    return node, depth

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

roots = [Node(i) for i in range(N)]
count = N

for i in range(M):
    x, y, z = map(int, input().split())
    x = roots[x-1]
    y = roots[y-1]
    if x.is_parent and y.is_parent:
            y.is_parent = False
            y.parent = x
            count -= 1
            x.childs.append(y)
    else:
        root_x, depth_x = root(x)
        root_y, depth_y = root(y)
        if root_x != root_y:
            if depth_x >= depth_y:
                root_y.is_parent = False
                root_y.parent = root_x
                count -= 1
                root_x.childs.append(root_y)
            else:
                root_x.is_parent = False
                root_x.parent = root_y
                count -= 1
                root_y.childs.append(root_x)

print(count)
### BUGGY CODE ###

#pypy
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.append(0)

#累積和
for _ in range(K):
    B = [0]*(N+1)
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1, i+A[i])
        B[l] += 1
        B[r+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    A = B
    if min(A) == N:
        break
A.pop()
print(*A)


### FIXED CODE ###

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

#累積和
for _ in range(K):
    B = [0]*N
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1, i+A[i])
        B[l] += 1
        if r+1 < N: B[r+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    B, A = A, B
    if min(A) == N:
        break

print(*A)
### BUGGY CODE ###

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

vlen = 0
for l1 in range(N):
    for l2 in range(l1+1, N):
        i = 0
        while l1 + i < l2 and l2 + i < N:
            if S[l1 + i] != S[l2 + i]:
                break
            i += 1
        vlen = max(i, vlen)
print(vlen)


### FIXED CODE ###

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

dp = [[None for j in range(N)] for i in range(N)]
vlen = 0
for i in range(N-1):
    for j in range(i + 1, N):
        if S[i] != S[j]:
            dp[i][j] = 0
        elif i - 1 >= 0 and j - 1 >= 0:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = 1
        if i + dp[i][j] <= j:
            vlen = max(vlen, dp[i][j])
print(vlen)
### BUGGY CODE ###

s = input()

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = (((ABC)%D *3)%D + (AB)%D)%D
        AB *= 3#AB + C and AB + B and AB + C
        AB += A[1] # AB + B
        A[1] = A[1]*3 + A[0]
        A[0] *= 3

print(ABC%D) 


### FIXED CODE ###

s = input()

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = (((ABC%D) *3)%D + (AB)%D)%D
        AB = (((AB%D) *3)%D + (A[1])%D)%D
        A[1] = (((A[1]%D)*3)%D + A[0]%D)%D
        A[0] = ((A[0]%D) * 3)%D

print(ABC%D)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = [0]*n

for i in range(n):
    tmp = A.index(i+1)
    ans[i] = tmp+1
    
print(' '.join([str(n) for n in ans]))

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = [0]*n

for i,j in enumerate(A):
    ans[j-1] = i+1    
print(' '.join([str(n) for n in ans]))
### BUGGY CODE ###

# qiitaにはbit全探索とは書いてないけど、bitが良さげ。
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

n = int(input())
fac_list = factorization(n)

p = []
for i in range(len(fac_list)):
    for j in range(fac_list[i][1]):
        p.append(fac_list[i][0])

l = n
for i in range(2 ** len(p)):
    a = 1
    for j in range(len(p)):
        if ((i >> j) & 1):
            a *= p[j]
    b = int(n/a)
    l = min(l, max(len(str(a)),len(str(b))))
print(l)

### FIXED CODE ###

# qiitaにはbit全探索とは書いてないけど、bitが良さげ。
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

n = int(input())
fac_list = factorization(n)

p = []
for i in range(len(fac_list)):
    for j in range(fac_list[i][1]):
        p.append(fac_list[i][0])

l = n
for i in range(2 ** len(p)):
    a = 1
    for j in range(len(p)):
        if ((i >> j) & 1):
            a *= p[j]
    b = int(n/a)
    l = min(l, max(len(str(a)),len(str(b))))
print(l)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [set() for _ in range(n)]
eb = [set() for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].add((u,a))
    ea[u].add((v,a))
    eb[v].add((u,b))
    eb[u].add((v,b))


def dijkstra(e,n,s):
    d = [None]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v] is not None and d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u] is None or d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = []
m = None
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    if m is None:
        m = r
    else:
        m = min(m,r)

    res.append(m)

res.reverse()
for r in res:
    print(10**15 - r)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    g[u].append((v,(a,b)))
    g[v].append((u,(a,b)))

inf = 10**18
def dijkstra(s, currency):
    d = [inf]*(n+1)
    d[s] = 0

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

for r in res:
    print(10**15-r)
### BUGGY CODE ###

import sys

def main():
	input = sys.stdin.readline

	N, M = list(map(int,input().strip().split()))
	A = list(map(int,input().strip().split()))
	A.sort(reverse=True)

	for i in range(M):
		A[0] = A[0]/2

		# larger = N
		# smaller = -1
		# while larger-smaller!=1:
		# 	ind = int((larger+smaller)/2)
		# 	if A[0]>A[ind]:
		# 		smaller = ind
		# 	else:
		# 		larger = ind

		# A.insert(larger,A[0])

		ind = 0
		if N!=1:
			while A[ind]<A[ind+1]:
				A[ind], A[ind+1] = A[ind+1], A[ind]
				ind = ind+1
				if ind==N-1:
					break

	print(sum(map(int,A)))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
	input = sys.stdin.readline

	N, M = list(map(int,input().strip().split()))
	A = list(map(int,input().strip().split()))
	A.sort(reverse=True)

	count = [0]*N
	ind = [0]
	for i in range(M):
		maximum = 0
		for j in ind:
			if A[j]>maximum:
				maxind = j
				maximum = A[j]

		if maximum==0: break

		# print(maxind)
		A[maxind] = A[maxind]/2
		count[maxind] += 1
		# print(count[maxind])
		if count[maxind]==len(ind):
			ind.append(0)
			# ind[-2] += 1
			ind[-2] = min(N-1,ind[-2]+1)
			# if ind[-1]!=N-1:
		else: 
			# ind[count[maxind]-1] += 1
			ind[count[maxind]-1] = min(N-1,ind[count[maxind]-1]+1)

		# print(ind)

	print(sum(map(int,A)))

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

n = int(input())
s = input()

dp = [[[0 for _ in range(1000)] for _ in range(4)] for _ in range(n+1)]
dp[0][0][0] = 1
ans = 0

for i in range(n):
    for j in range(4):
        for k in range(1000):
            if dp[i][j][k] == 0: continue
            dp[i+1][j][k] = 1
            if j <= 2:
                dp[i+1][j+1][k*10 + int(s[i])] = 1

print(sum(dp[n][3]))


### FIXED CODE ###

n = int(input())
s = input()

ones = set()
twos = set()
threes = set()

for a in s:
    for item in twos:
        threes.add(item+a)
    for item in ones:
        twos.add(item+a)
    ones.add(a)

print(len(threes))
### BUGGY CODE ###

n,k=map(int,input().split())
sushi=[]
for i in range(n):
    sushi.append([])
for i in range(n):
    t,d=map(int,input().split())
    sushi[t-1].append(d)
Max=[]
Rest=[]
v=0
for i in sushi:
    if not i==[]:
        Max.append(max(i))
        i.remove(max(i))
        Rest=Rest+i
        v=v+1
Max.sort(reverse=True)
Rest.sort(reverse=True)
Max_s=[]
Rest_s=[0]
Sum=0
for i in Max:
    Sum=Sum+i
    Max_s.append(Sum)
Sum=0
for i in Rest:
    Sum=Sum+i
    Rest_s.append(Sum)
ans=0
l_r=len(Rest)
for i in range(1,min(k,v)+1):
    if k-i<=l_r:
        temp=Max_s[i-1]+Rest_s[k-i]+i**2
        if ans<temp:
            ans=temp
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
sushi=[]
for i in range(n):
    sushi.append([])
for i in range(n):
    t,d=map(int,input().split())
    sushi[t-1].append(d)
Max=[]
Rest=[]
v=0
for i in sushi:
    if not i==[]:
        Max.append(max(i))
        i.remove(max(i))
        for j in i:
            Rest.append(j)
        v=v+1
Max.sort(reverse=True)
Rest.sort(reverse=True)
Max_s=[]
Rest_s=[0]
Sum=0
for i in Max:
    Sum=Sum+i
    Max_s.append(Sum)
Sum=0
l_r=0
for i in Rest:
    Sum=Sum+i
    Rest_s.append(Sum)
    l_r=l_r+1
ans=0
for i in range(1,min(k,v)+1):
    if k-i<=l_r:
        temp=Max_s[i-1]+Rest_s[k-i]+i**2
        if ans<temp:
            ans=temp
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import math
N = int(input())

def divisor(N):
    lst = []
    for i in range(2,N):
        if N%i == 0:
            lst.append(i)
    #print(lst)
    if len(lst)%2 == 0:
        middle = int(len(lst) / 2)
        #print(lst[middle])
        return lst[middle]
    else:
        middle = int(len(lst) / 2)
        #print(lst[middle])
        return lst[middle]

    
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True
  
if isPrime(N):
    print(N-1)
else:
    ans = divisor(N)
    A = ans
    B = N/ans
    print(int(A+B-2))#
#print(ans)
        

### FIXED CODE ###

# coding: utf-8
# Your code here!
import math
import sys
N = int(input())

def divisor(N):
    lst = []
    for i in range(2,math.ceil(math.sqrt(N))+1):
        if N%i == 0:
            lst.append(i)
            #if i != int(N/i):
                #lst.append(int(N/i))
    #lst.sort()
    return lst
    
ans = divisor(N)
#print(ans,len(ans))
if N == 2:
    print(1)
    sys.exit()
    
if len(ans) > 0:
    A = ans[-1]
    if A*A < N:
        B = int(N/A)
        print(A+B-2)
    else:
        print(2*A-2)
else:
    print(N-1)

'''
if len(ans)%2 == 0 and len(ans)>1:
    A = ans[len(ans)//2-1]
    B = ans[len(ans)//2]
    #print(A,B)
    print(A+B-2)
elif len(ans)%2 == 1 and len(ans)>1:
    A = ans[len(ans)//2]
    print(2*A-2)
else:
    print(N-1)
'''
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
A = [I() for _ in range(M)]
md = 10**9+7

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

for now in range(N):
  for next in range(now+1, now+3):
    if next == N:
      dp[next] += dp[now]
      dp[next] %= md
      break
    if next in A:
      continue
    else:
      dp[next] += dp[now]
      dp[next] %= md

print(dp[N])

### FIXED CODE ###

#import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
A = [I() for _ in range(M)]
md = 10**9+7


dp = [0] * (N+1)
dp[0] = 1
chk = [True] * (N+1)
for a in A:
  chk[a] = False

for now in range(N):
  for next in range(now+1, now+3):
    if next == N:
      dp[next] += dp[now]
      dp[next] %= md
      break
    if not chk[next]:
      continue
    else:
      dp[next] += dp[now]
      dp[next] %= md

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

N, K = (int(i) for i in input().split())

L = []
for i in range(N):
    a, b = (int(i) for i in input().split())
    L = L + [a]*b
    if len(L) > K:
        L.sort()
        L = L[:K]
        if L[-1] == 1:
            print(1)
            break
else:
    print(L[-1])

### FIXED CODE ###

N, K = (int(i) for i in input().split())

D = {}
count = 0
for i in range(N):
    a, b = (int(i) for i in input().split())
    if a in D:
        D[a] += b
    else:
        D[a] = b

else:
    aL = [a for a in D.keys()]
    aL.sort()
    for a in aL:
        count += D[a]
        if count >= K:
            print(a)
            break
### BUGGY CODE ###

def main():
    N = int(input())
    P = list(map(int,input().split()))
    cnt = 0
    for i in range(N):
        # Pi
        # P[0:i]
        Q = [ _ for _ in P[0:i] if P[i] <= _ ]
        #for _ in P[0:i+1]:
        #    print(_)
        if len(Q) == i:
            cnt += 1
    print(cnt)

main()

### FIXED CODE ###

def main():
    N = int(input())
    P = list(map(int,input().split()))
    cnt = 0
    Q = max(P)
    for i in range(N):
        if Q >= P[i]:
            cnt += 1
            Q = P[i]
    print(cnt)

main()
### BUGGY CODE ###

n = int(input())
DP = [[[-1 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]


def f(i, j, k):
    if DP[i][j][k] != -1:
        return DP[i][j][k]
    if i+j+k == 0:
        return 0
    tmp = 0
    if i > 0:
        tmp += i*f(i-1, j, k)
    if j > 0:
        tmp += j*f(i+1, j-1, k)
    if k > 0:
        tmp += k*f(i, j+1, k-1)
    tmp += n
    tmp /= i+j+k
    DP[i][j][k] = tmp
    return tmp


*A, = map(int, input().split())
i, j, k = A.count(1), A.count(2), A.count(3)
print(f(i, j, k))


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0:
                tmp += DP[i+1][j-1][k]*j
            if k > 0:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main(A, N):
    d1 = defaultdict(int)
    d2 = defaultdict(int)

    for i, a in enumerate(A):
        d1[i+a] += 1
    
    for i, a in enumerate(A):
        d2[i-a] += 1

    mn_x = min(min(d1.keys()), min(d2.keys()))
    mx_x = max(max(d1.keys()), max(d2.keys()))

    cnt = 0
    for x in range(mn_x, mx_x+1):
        cnt += d1[x]* d2[x]

    print(cnt)
    pass

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    main(A, N)


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main(A, N):
    d1 = defaultdict(int)
    d2 = defaultdict(int)

    for i, a in enumerate(A):
        d1[i+a] += 1
    
    for i, a in enumerate(A):
        d2[i-a] += 1

    cnt = 0
    for x in list(d1.keys())+list(d2.keys()):
        cnt += d1[x]* d2[x]

    print(cnt//2)
    pass

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    main(A, N)