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

n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
def search(arr,target,start,last):
 #   print("target ==",target,arr[start:last+1])
    if last - start == 1:
        if(arr[last] < target):
            return last
        elif(arr[start] < target):
            return start
        else:
            return -1
    if last < start:
        return -1
    if start == last:
        if arr[start] < target:
            return start
        else:
            return -1
    mid = (last - start)//2 + start
    if arr[mid] < target:
        return search(arr,target,mid + 1,last)
    else:
        return search(arr,target,start,mid)
    return -1


for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a + b 
  #      print("#",a,b)
        f1 = search(l,target,j+1,n-1)
        if f1 == -1: 
            continue
   #     print("arr[f1]",l[f1])
        cnt+= f1 - j 
   #     print("cnt: ",cnt)
print(cnt)


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
import bisect
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a + b 
  #      print("#",a,b)
        f1 = bisect.bisect_left(l,target,j+1,n)
        cnt+= f1 - 1- j
   #     print("cnt: ",cnt)
print(cnt)
### BUGGY CODE ###

T = int(input())

for i in range(T):
  a, b, c, d = map(int, input().split())
  if d<b or a<b:
    print('No')
    continue
  if b-1<=c:
    print('Yes')
    continue
  if d%b<b-c and d%b!=0:
    print('No')
    continue
  for j in range(c):
    if a>c:
      a = c+(a-c)%b
    if a>c and a<b:
      print('No')
      break
    else:
      if a==c:
        a = a-b
    a+=d
    if j==c-1:
      print('Yes')




### FIXED CODE ###

import fractions
T = int(input())

for i in range(T):
  a, b, c, d = map(int, input().split())

  if d<b or a<b:
    print('No')
    continue

  if b-1<=c:
    print('Yes')
    continue

  gcd=fractions.gcd(d,b)
  e=b-gcd+a%gcd
  if e>c:
    print('No')
  else:
    print('Yes')
### BUGGY CODE ###

k = int(input())
def gcd(a, b):
    while b > 0:
        r = a%b
        a = b
        b = r
    return a
s = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        a = gcd(i,j)
        for z in range(1,k+1):
            s+=gcd(a,z)
print(s)

### FIXED CODE ###

from math import gcd
k = int(input())
s = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        a = gcd(i,j)
        for z in range(1,k+1):
            s+=gcd(a,z)
print(s)
### BUGGY CODE ###

import math

n = int(input())

ans = 0

for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            ans += math.gcd(math.gcd(i, j), k)

print(ans)


### FIXED CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


n = int(input())

ans = 0

for i in range(1, n + 1):
    for j in range(i, n + 1):
        for k in range(j, n + 1):
            cnt = gcd(i, j, k)
            if i == j and j == k:
                ans += cnt
            elif (i == j and i != k) or (i == k and i != j) or (j == k and j != i):
                ans += cnt * 3
            else:
                ans += cnt * 6

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

from sys import stdin
import fractions
import sys
sys.setrecursionlimit(10**6) 

n,x = [int(x) for x in stdin.readline().rstrip().split()]

li = list(map(int,stdin.readline().rstrip().split()))

def gcd_all(list):
    return gcd_all([fractions.gcd(*list[:2])] + list[2:]) if len(list) > 1 else list[0]
lin = []
for i in range(len(li)):
    lin.append(abs(li[i]-x))
gcd = gcd_all(lin)
print(gcd)

### FIXED CODE ###

from sys import stdin
import fractions


n,x = [int(x) for x in stdin.readline().rstrip().split()]

li = list(map(int,stdin.readline().rstrip().split()))
lin = []
for i in range(len(li)):
    lin.append(abs(li[i]-x))
poi = lin[0]
for i in range(len(lin)-1):
    poi = fractions.gcd(poi,lin[i+1])

print(poi)
### BUGGY CODE ###

N = int(input())
As = [int(n) for n in input().split()]

vals = {}
for A in As:
    if A in vals:
        vals[A] += 1
    else:
        vals[A] = 1

def waystochoose(k):
    total = 0
    for val in vals:
        if val == k:
            total += (vals[val] - 1)*(vals[val] - 2) // 2
        else:
            total += vals[val]*(vals[val]-1) // 2
    return total

checked = {}
for k in range(len(As)):
    if not As[k] in checked:
        ways = waystochoose(As[k])
        print(ways)
        checked[As[k]] = ways
    else:
        print(checked[As[k]])


### FIXED CODE ###

N = int(input())
As = [int(n) for n in input().split()]

vals = {}
for A in As:
    if A in vals:
        vals[A] += 1
    else:
        vals[A] = 1

#print(vals)

choose2 = {}
for val in vals:
    num = vals[val]
    choose2[val] = num*(num - 1) // 2

#print(choose2)

total = 0
for k in choose2:
    total += choose2[k]
#print("total: " + str(total))

for Ak in As:
    print(total - (vals[Ak] - 1))
### BUGGY CODE ###

input()
a = list(map(int,input().split()))
ans = 1
for n in a:
    ans *= n
if ans <= 10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

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

if 0 in a:
    print(0)
    exit()

ans = 1
for n in a:
    ans*=n
    
    if ans > 10**18:
        ans = -1
        break
    
print(ans)
### BUGGY CODE ###

a, b = map(int, input().split())
ans = a
abl = set(range(a + 1, b + 1))
for ab in abl:
    ans = ans ^ ab
print(ans)

### FIXED CODE ###

a, b = map(int, input().split())
if a == b:
    ans = a
elif a % 2 == 0:
    if (b - a) % 4 == 0:
        ans = 0 ^ b
    elif (b - a) % 4 == 2:
        ans = 1 ^ b
    elif (b - a) % 4 == 1:
        ans = 1
    else:
        ans = 0
else:
    if (b - a) % 4 == 0:
        ans = a ^ 0
    elif (b - a) % 4 == 2:
        ans = a ^ 1
    elif (b - a) % 4 == 1:
        ans = a ^ 0 ^ b
    else:
        ans = a ^ 1 ^ b
print(ans)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
n=int(input())
a=[int(i) for i in input().split()]
x=[]
for i in range(1,n+1):
    b=a.pop(-i)
    x.append(reduce(gcd,a))
    a.append(b)
print(max(x))

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=[int(i) for i in input().split()]
l=[0]*n
r=[0]*n
for i in range(n-1):
    l[i+1]=gcd(l[i],a[i])
    r[i+1]=gcd(r[i],a[n-i-1])
r=r[::-1]
g=[]
for i in range(n):
    g.append(gcd(l[i],r[i]))
print(max(g))
### BUGGY CODE ###

from decimal import Decimal

n, k = map(int, input().split())
sum = Decimal(0.0)
for i in range(1, n + 1):
    p = Decimal(1.0 / n)
    score = i
    while score < k:
        score = score * 2
        p = p * Decimal(0.5)
    sum += p
print(str(sum)[:14])


### FIXED CODE ###

n, k = map(int, input().split())
sum = 0.0
for i in range(1, n + 1):
    p = 1.0 / n
    score = i
    while score < k:
        score = score * 2
        p = p * 0.5
    sum += p
print(sum)
### BUGGY CODE ###

def main():
	n, m = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	
	d = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
	num2match = {key:val for key, val in d.items() if key in nums}
	
	dp = [-1 for i in range(n + 1)]

	dp[0] = 0
	val_set = set(num2match.values())
	match2num = {v:max([int(key) for key, val in num2match.items() if val == v]) for v in val_set}
 
	for i in range(2, n + 1):
		for val in val_set:
			if i >= val and dp[i - val] > 0:
				tmp = match2num[val] * (10 ** len(str(dp[i - val]))) + dp[i - val]
				dp[i] = max(dp[i], tmp)
			elif i >= val and dp[i - val] == 0:
				tmp = match2num[val]
				dp[i] = max(dp[i], tmp)
	
	#print(num2match)
	#print(match2num)
	#print(dp)
	print(int(dp[n]))
 
if __name__ == '__main__':
	main()

### FIXED CODE ###

import math
def main():
	n, m = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	
	d = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
	num2match = {key:val for key, val in d.items() if key in nums}
	
	dp = [-1 for i in range(n + 1)]
	dp_keta = [0 for i in range(n + 1)]

	dp[0] = 0
	val_set = list(set(num2match.values()))
	match2num = {v:max([int(key) for key, val in num2match.items() if val == v]) for v in val_set}

	cnt = 0
	for i in range(2, n + 1):
		for val in val_set:
			#print(val)
			cnt += 1
			if i >= val and dp[i - val] >= 0:
				tmp = match2num[val] * (10 ** dp_keta[i - val]) + dp[i - val]
				dp[i] = max(dp[i], tmp)
				dp_keta[i] = max(dp_keta[i], dp_keta[i - val] + 1)

	#print(num2match)
	#print(match2num)
	#print(dp)
	#print(dp)
	print(int(dp[n]))
	#print(cnt)
 
if __name__ == '__main__':
	main()
### BUGGY CODE ###

k,s = map(int,input().split())
count =0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if((x+y+z) == s):
                count +=1

print(count)


### FIXED CODE ###

k,s = map(int,input().split())
count =0

for x in range(k+1):
    for y in range(k+1):
        if (((s-x-y) <=k) and (0 <= (s-x-y))):
            count +=1
print(count)
### BUGGY CODE ###

s = input()
n = int(input())
re = 1

for i in range(n):
    q = input().split()
    if q[0] == '1':
        re = re * -1
    else:
        if re == 1:
            if q[1] == '1':
                s = q[2] + s
            else:
                s = s + q[2]
        else:
            if q[1] == '1':
                s = s + q[2]
            else:
                s = q[2] + s

print(s) if re == 1 else print(s[::-1])

### FIXED CODE ###

s = input()
n = int(input())
re = 1
head = ''
tail = ''

for i in range(n):
    q = input().split()
    if q[0] == '1':
        re = re * -1
    else:
        if re == 1:
            if q[1] == '1':
                head = q[2] + head
            else:
                tail = tail + q[2]
        else:
            if q[1] == '1':
                tail = tail + q[2]
            else:
                head = q[2] + head

print(head+s+tail) if re == 1 else print((head+s+tail)[::-1])
### BUGGY CODE ###

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

	ans = [0] * (10 ** 5 + 1)

	for X in range(10 ** 5 + 1):
		if X == 0:
			ans[0] += a.count(0)
			ans[0] += a.count(1)
		elif X == 10 ** 5:
			ans[10 ** 5] += a.count(10 ** 5 - 1)
			ans[10 ** 5] += a.count(10 ** 5 + 1)
		else:
			ans[X] += a.count(X - 1)
			ans[X] += a.count(X)
			ans[X] += a.count(X + 1)

	print(max(ans))

 
if __name__ == "__main__":
  	main()

### FIXED CODE ###

def main():
	N = int(input())
	a = list(map(int, input().split()))
	
	a_lst = [0] * (10 ** 5 + 1)
	for num in a:
		a_lst[num] += 1

	ans = 0
	for X in range(10 ** 5 + 1):
		cnt = 0

		if X == 0:
			cnt += a_lst[X]
			cnt += a_lst[X + 1]
		elif X == 10 ** 5:
			cnt += a_lst[X - 1]
			cnt += a_lst[X]
		else:
			cnt += a_lst[X - 1]
			cnt += a_lst[X]
			cnt += a_lst[X + 1]

		if cnt > ans:
			ans = cnt

	print(ans)



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

n = int(input())
s = input()
ans = 0

for i in range(n):
    si = s[i]
    for j in range(i+1, n):
        sj = s[j]
        if si == sj:
            continue
        else:
            for k in range(j+1, n):
                sk = s[k]
                if j - i != k - j and sj != sk and sk != si:
                    ans += 1
print(ans)

### FIXED CODE ###

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

ans = s.count('R') *  s.count('G') *  s.count('B')

for i in range(n):
    for j in range(i+1, n):
        k = 2 * j - i

        if k >= n:
            break
        elif s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1
         
print(ans)
### BUGGY CODE ###

from collections import deque

H,W=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
field=[list(input()) for _ in range(H)]
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1

Walk=[[1,0],[0,1],[-1,0],[0,-1]]
Warp=[[i,j] for i in range(-2,3) for j in range(-2,3)] 

dist=[[-1]*W for _ in range(H)]
que=deque()
dist[sy][sx]=0
que.append([sy,sx])

while que:
    y,x=que.popleft()
    for walk in Walk:
        nx,ny=x+walk[0],y+walk[1]
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if field[ny][nx]=="#": continue
        if dist[ny][nx]!=dist[y][x]:
            dist[ny][nx]=dist[y][x]
            que.appendleft([ny,nx])
    
    for warp in Warp:
        nx,ny=x+warp[0],y+warp[1]
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if field[ny][nx]=="#": continue
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

print(dist[gy][gx])


### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
field=[list(input()) for _ in range(H)]
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1

Walk=[[1,0],[0,1],[-1,0],[0,-1]]
Warp=[[i,j] for i in range(-2,3) for j in range(-2,3)] 

dist=[[-1]*W for _ in range(H)]
que=deque()
dist[sy][sx]=0
que.append([sy,sx])

while que:
    y,x=que.popleft()
    for walk in Walk:
        nx,ny=x+walk[0],y+walk[1]
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if field[ny][nx]=="#": continue
        if dist[ny][nx]!=dist[y][x]:
            dist[ny][nx]=dist[y][x]
            que.appendleft([ny,nx])
    
    for warp in Warp:
        nx,ny=x+warp[0],y+warp[1]
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if field[ny][nx]=="#": continue
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

print(dist[gy][gx])
### BUGGY CODE ###

import math
a,b,c=map(int,input().split())
d=[]
for i in range(0,c+1):
    e=math.floor(a*i/b)-a*math.floor(i/b)
    d.append(e)
d.sort()
print(d[-1])


### FIXED CODE ###

import math
a,b,c=map(int,input().split())
if b>c:
    print(math.floor((a*c)/b)-a*(math.floor(c/b)))
else:
    print(math.floor((a*(b-1))/b)-a*(math.floor((b-1)/b)))
### BUGGY CODE ###

from fractions import gcd

Mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))

def lcm(x,y):
    return x*y//gcd(x,y)

lm = A[0]
for a in A[1:]:
    lm = lcm(lm, a)

ans = 0
for i in range(N):
    ans += ( lm//A[i] )
    ans %= Mod

print(ans)

### FIXED CODE ###

from fractions import gcd

Mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))

lm = A[0]
for a in A[1:]:
    lm = lm*a//gcd(lm,a)

ans = 0
for i in range(N):
    ans += lm//A[i]
ans %= Mod

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

#https://atcoder.jp/contests/abc110/tasks/abc110_c

s = list(str(input()))
t = list(str(input()))
flag = 'Yes'
jskip = []
l = len(s)
for i in range(l):
    f = True
    for j in range(len(jskip)):
        if jskip[j] == s[i]:
            f = False
            break
    if f == True:
        for j in range(l):
            if s[i] == s[j] and t[i] != t[j]:
                flag = 'No'
                break
            elif t[i] == t[j] and s[i] != s[j]:
                flag = 'No'
                break
            elif s[i] == s[j] and t[i] == t[j]:
                jskip.append(s[i])
            if flag == 'No':
                break
    if flag == 'No':
        break

print(flag)


### FIXED CODE ###

import sys
s = str(input())
t = str(input())
l = len(s)
tmp = [[], []]
for i in range(l):
    if (not s[i] in tmp[0]) and (not t[i] in tmp[1]):
        tmp[0].append(s[i])
        tmp[1].append(t[i])
    else:
        if s[i] in tmp[0]:
            tmp2 = 0
            for j in range(len(tmp[0])):
                if s[i] == tmp[0][j]:
                    tmp2 = j
            if t[i] != tmp[1][tmp2]:
                print('No')
                sys.exit()
        else:
            print('No')
            sys.exit()
print('Yes')
### BUGGY CODE ###

#11
n = int(input())
a = list(map(int, input().split()))
 
flag = [a.count(a[i])-1 for i in range(n+1) ]
p = flag.index(1) + list(reversed(flag)).index(1)
 
mod = 10**9+7
    
def memoize(f): #メモ化関数
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def easyFact(n):
    if ( n==0 ): 
        return 1
    else: 
        return n*easyFact(n-1)

g = [easyFact(i) for i in range(n+3)]

def combination(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return ( g[n] /( g[r] * g[n-r] ) )
 
 
for i in range(n+1):
    if ( p>=i ):
        c =( combination(n+1, i+1) - combination(p, i) ) % mod
    else:
        c =( combination(n+1, i+1) ) % mod
    print( int(c) )

### FIXED CODE ###


MOD = 10**9+7
n = int(input())
la = list(map(int,input().split()))
L = [-1]*(n+1)
l = 0
for i in range(n+1):
  a = la[i]
  if L[a] == -1:
    L[a] = i
  else:
    l = i - L[a] - 1
    break
 
MAX = n
factorial = [1, 1]
inverse = [0, 1]
inverse_factorial = [1, 1]
for i in range(2,MAX+1):
  factorial.append( (factorial[-1]*i)%MOD )
  inverse.append( (-inverse[MOD%i]*(MOD//i))%MOD )
  inverse_factorial.append( (inverse_factorial[-1]*inverse[-1])%MOD )
 
def C_MOD(n, k):
  if k < 0 or k > n:
    return 0
  k = min(k,n-k)
  return factorial[n] * inverse_factorial[k] * inverse_factorial[n-k] % MOD
 
print(n)
#print((2*C_MOD(n-1,1)-C_MOD(n-1-l,1)+C_MOD(n-1,2)+1)%MOD)
for i in range(2,n+1):
  if n > l+1:
    print((2*C_MOD(n-1,i-1)-C_MOD(n-1-l,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
  else:
    print((2*C_MOD(n-1,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
print(1)
### BUGGY CODE ###

n= int(input())
A = list(map(int, input().split()))
q = int(input())
Mi = list(map(int, input().split()))

def solve(i,m):
 if m == 0:
  return True
 if i >= n:
  return False
 res = solve(i+1, m) or solve(i + 1, m - A[i])
 return res

for m in Mi:
 for i in range(n):
  if solve(i, m):
   print("yes")
   break
  if i == n-1 and not(solve(i,m)):
   print("no")

### FIXED CODE ###

n= int(input())
A = list(map(int, input().split()))
q = int(input())
Mi = map(int, input().split())
PS={}
def solve(i,m):
 if m == 0:
  return True
 if (i,m) in PS:
  return PS[(i,m)]
 if i >= n:
  return False
 res = solve(i+1, m) or solve(i + 1, m - A[i])
 PS[(i,m)] = res
 return res

for m in Mi:
 if solve(0, m):
  print("yes")
 else:
  print("no")
### BUGGY CODE ###

import math
N=int(input())
c=[]
for i in range(math.ceil((4*N)**(1/2)-2), N):
    for k in range(1, i+1):
        if (1+k)*(i+1-k)==N:
            c.append(i)
print(min(c))

### FIXED CODE ###

import math
N=int(input())
c=[]
flag=0
for x in range(1, math.ceil(pow(N,1/2))+1):
    if N%x==0:
        c.append(x+N//x-2)
print(min(c))
### BUGGY CODE ###

*j, n = map(int, input().split())
j.sort()
a, b, c = j
count = 0
for y in range(n//b+1):
    for z in range((n-y*b)//c+1):
        if (n - b*y - c*z) % a == 0 and (n - b*y - c*z) >= 0:
            count += 1
print(count)

### FIXED CODE ###

*j, n = map(int, input().split())
j.sort()
a, b, c = j
count = 0
for y in range(n//b+1):
    for z in range((n-y*b)//c+1):
        if (n - b*y - c*z) % a == 0:
            count += 1
print(count)
### BUGGY CODE ###

def main():
    from collections import Counter
    import sys

    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    def f(c1, c2, c3):
        ind = c1 * x1 + c2 * x2 + c3
        if dp[ind] != -1.0:
            return dp[ind]

        res = (n \
               + (f(c1 - 1, c2, c3) * c1 if c1 > 0 else 0) \
               + (f(c1 + 1, c2 - 1, c3) * c2 if c2 > 0 else 0) \
               + (f(c1, c2 + 1, c3 - 1) * c3 if c3 > 0 else 0)) \
              / (c1 + c2 + c3)

        dp[ind] = res
        return res

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [-1.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    print(f(c1, c2, c3))


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
### BUGGY CODE ###

N = int(input())
a_list = [int(i) for i in input().split()]

for i in range(1, N + 1):
    print(sum(a == i for a in a_list[i - 1:]))


### FIXED CODE ###

from collections import defaultdict

N = int(input())
a_dict = defaultdict(int)
for i in input().split():
    a_dict[int(i)] += 1

for i in range(1, N + 1):
    print(a_dict[i])
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
L = []

for i in A:
    cnt = 0
    while i!=0 or cnt<M:
        L.append(i-i//2)
        i//=2
        cnt+=1

L.sort(reverse=True)
print(sum(A)-sum(L[:M]))

### FIXED CODE ###

import heapq
from math import ceil
n,m = map(int,input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)

for i in range(m):
    heapq.heappush(a,ceil(heapq.heappop(a)/2))

print(-sum(a))
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    query = input().split()
    if int(query[0]) == 1:
        S = S[::-1]
    elif int(query[0]) == 2:
        if int(query[1]) == 1:
            S = query[2] + S
        elif int(query[1]) == 2:
            S = S +query[2]
print(S)

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
reversecount = 0
d = deque(S)
for x in query:
    if int(x[0]) == 1:
        reversecount += 1
    else:
        if (int(x[1]) == 1 and (reversecount % 2 == 0)) or (int(x[1]) == 2 and (reversecount % 2 == 1)):
            d.appendleft(x[2])
        else:
            d.append(x[2])
if reversecount % 2 == 1:
    d.reverse()
print(*d, sep='')
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
is_neighbor = [[True] * n for i in range(n)]

f = True
for i in range(n):
    if not f: break
    for s in range(n):
        if not f: break
        for t in range(n):
            if a[s][t] > a[s][i] + a[i][t]:
                f = False
                break
            elif i == s or i == t: continue
            elif a[s][t] == a[s][i] + a[i][t]:
                is_neighbor[s][t] = False
if f:
    ans = 0
    for i in range(n):
        for j in range(n):
            if is_neighbor[i][j]:
                ans+=a[i][j]
    print(ans//2)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
is_neighbor = [[True] * n for i in range(n)]

f = True
for i in range(n):
    if not f: break
    for s in range(n):
        if not f: break
        for t in range(n):
            if a[s][t] > a[s][i] + a[i][t]:
                f = False
                break
            elif i == s or i == t: continue
            elif a[s][t] == a[s][i] + a[i][t]:
                is_neighbor[s][t] = False
if f:
    ans = 0
    for i in range(n):
        for j in range(n):
            if is_neighbor[i][j]:
                ans+=a[i][j]
    print(ans//2)
else:
    print(-1)