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

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

I = a.count(1)
J = a.count(2)
K = a.count(3)

dp = [[[0 for _ in range(n+1)] for __ in range(n+1)] for ___ in range(n+1)]

for k in range(K+1):
    for j in range(J+K+1):
        for i in range(I+J+K+1):
            if i == 0 and j == 0 and k == 0:
                continue
            if k-1 > -1 and j+1 < n+1:
                dp[i][j][k] += (n/(i+j+k))*(k/n)*dp[i][j+1][k-1]
            if j-1 > -1 and i+1 < n+1:
                dp[i][j][k] += (n/(i+j+k))*(j/n)*dp[i+1][j-1][k]
            if i-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(i/n)*dp[i-1][j][k]
            dp[i][j][k] += n/(i+j+k)

print(dp[I][J][K])


### FIXED CODE ###

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

I = a.count(3)
J = a.count(2)
K = a.count(1)

dp = [[[0 for _ in range(I+J+K+1)] for __ in range(I+J+1)]
      for ___ in range(I+1)]

for i in range(I+1):
    for j in range(I+J+1-i):
        for k in range(I+J+K+1-i-j):
            if i + j + k == 0:
                continue
            if k-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(k/n)*dp[i][j][k-1]
            if j-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(j/n)*dp[i][j-1][k+1]
            if i-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(i/n)*dp[i-1][j+1][k]
            dp[i][j][k] += n/(i+j+k)

print(dp[I][J][K])
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(x, k+1):
        for z in range(y, k+1):
            if x + y + z == s:
                if x == y == z:
                    count += 1
                elif x != y and y != z and z != x:
                    count += 6
                else:
                    count += 3
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-k <= x + y <= s:
            count += 1
print(count)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    x,y,z=map(int,input().split())
    a.append((x-1,y-1,z))

class union:
    def __init__(self,num):
        self.par=[-1]*num
    def get_par(self,node):
        if self.par[node]==-1:
            return node
        else:
            x=self.get_par(self.par[node])
            return x
    def merge(self,x,y):
        X=self.get_par(x)
        Y=self.get_par(y)
        if X!=Y:
            self.par[Y]=X
    def output(self):
        print(self.par)
    def count(self):
        print(self.par.count(-1))
u=union(n)
for i in range(m):
    u.merge(a[i][0],a[i][1])
u.count()


### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    x,y,z=map(int,input().split())
    a.append((x-1,y-1))

class union:
    def __init__(self,num):
        self.par=[-1]*num
    def get_par(self,node):
        if self.par[node]==-1:
            return node
        else:
            x=self.get_par(self.par[node])
            return x
    def merge(self,x,y):
        X=self.get_par(x)
        Y=self.get_par(y)
        if X!=Y:
            self.par[Y]=X
    def output(self):
        print(self.par)
    def count(self):
        print(self.par.count(-1))
def get_parent(node):
    if par[node]==-1:
        return node
    else:
        par[node]=get_parent(par[node])
        return par[node]
    
def merge(x,y):
    i=get_parent(x)
    j=get_parent(y)
    if i!=j:
        par[i]=j
    return
par=[-1]*n
for i in range(m):
    merge(a[i][0],a[i][1])
print(par.count(-1))
### BUGGY CODE ###

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  p=[[0]*w for _ in range(h)]
  for _ in range(k):
    r,c,v=map(int,input().split())
    p[r-1][c-1]=v
  dp=[[[0]*4 for j in range(w)] for i in range(h)]
  if p[0][0]!=0:
    dp[0][0][1]=p[0][0]
  for y in range(h):
    for x in range(w):
      for i in range(4):
        if x<w-1:
          if dp[y][x+1][i]<dp[y][x][i]:
            dp[y][x+1][i]=dp[y][x][i]
          if i<3 and p[y][x+1]!=0 and dp[y][x+1][i+1]<dp[y][x][i]+p[y][x+1]:
            dp[y][x+1][i+1]=dp[y][x][i]+p[y][x+1]
        if y<h-1:
          if dp[y+1][x][0]<dp[y][x][i]:
            dp[y+1][x][0]=dp[y][x][i]
          if p[y+1][x]!=0 and dp[y+1][x][1]<dp[y][x][i]+p[y+1][x]:
            dp[y+1][x][1]=dp[y][x][i]+p[y+1][x]
  print(max(dp[h-1][w-1]))
main()

### FIXED CODE ###

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  H=range(h)
  W=range(w)
  dp=[[[0]*w for j in H] for i in range(4)]
  for _ in range(k):
    r,c,v=map(int,input().split())
    dp[0][r-1][c-1]=v
  if dp[0][0][0]!=0:
    dp[1][0][0]=dp[0][0][0]
    dp[0][0][0]=0
  for y in H:
    for x in W:
      v=dp[0][y][x]
      dp[0][y][x]=0
      for i in range(4):
        if 0<x:
          if dp[i][y][x]<dp[i][y][x-1]:
            dp[i][y][x]=dp[i][y][x-1]
          if 0<i and v!=0 and dp[i][y][x]<dp[i-1][y][x-1]+v:
            dp[i][y][x]=dp[i-1][y][x-1]+v
        if 0<y:
          if dp[0][y][x]<dp[i][y-1][x]:
            dp[0][y][x]=dp[i][y-1][x]
          if v!=0 and dp[1][y][x]<dp[i][y-1][x]+v:
            dp[1][y][x]=dp[i][y-1][x]+v
  print(max([dp[i][h-1][w-1] for i in range(4)]))
main()
### BUGGY CODE ###

def main():
    S = input()
    Q = int(input())
    reverse = False
    for _ in range(Q):
        query = input()
        if len(query) == 1:
            reverse = not reverse
        else:
            _, F, C = query.split()
            if (not reverse and F == '1') or (reverse and F == '2'):
                S = C + S
            else:
                S = S + C
    if reverse:
        S = S[::-1]
    print(S)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque


def main():
    S = input()
    que = deque(S)
    Q = int(input())
    reverse = False
    for _ in range(Q):
        query = input()
        if len(query) == 1:
            reverse = not reverse
        else:
            _, F, C = query.split()
            if (not reverse and F == '1') or (reverse and F == '2'):
                que.appendleft(C)
            else:
                que.append(C)
    if reverse:
        que.reverse()
    print(''.join([c for c in que]))


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

n = int(input())
s = [input() for _ in range(n)]

d = {}
for i in range(n):
  if s[i] in d.keys():
    d[s[i]] += 1
  else:
    d[s[i]] = 1

m = max(d.values())

ans = [k for k, v in d.items() if v == m]

for i in sorted(ans):
  print(i)

### FIXED CODE ###

from collections import Counter

n = int(input())
s = [input() for _ in range(n)]

c = Counter(s)
c = c.most_common()
ans_number = c[0][1]
c.sort()

for i in range(len(c)):
  if c[i][1] == ans_number:
    print(c[i][0])
### BUGGY CODE ###

import numpy as np
n = int(input())
a =np.array([int(x) for x in input().split()])
q = int(input())
bc = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*bc)]

for i in range(q):
    a = np.sort(a)
    ans = 0
    for j in range(len(a)):
        if a[j] <= 10 **5:
            if a[j] == b[i]:
                a[j] = c[i]
        ans += a[j]
    print(ans)

### FIXED CODE ###

import numpy as np
import collections

n = int(input())
a =np.array([int(x) for x in input().split()])
q = int(input())
bc = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*bc)]

count_dict = collections.Counter(a)
ans = np.sum(a)
for i in range(q):
    if count_dict[b[i]] > 0:
        ans += count_dict[b[i]]*(c[i]-b[i])
        count_dict[c[i]] += count_dict[b[i]]
        count_dict[b[i]] = 0
    print(ans)
### BUGGY CODE ###

l, r = map(int, input().split())

LUT = [[(i*j)%2019 for i in range(2019)] for j in range(2019)]

ans = 2018
m = 2019
for i in range(l, r + 1):
  for j in range(i + 1, r + 1):
    ans = min(ans, LUT[i % m][j % m])
    if ans == 0:
      break
    
print(ans)


### FIXED CODE ###

def main():
  l, r = map(int, input().split())
  LUT = [[(i*j)%2019 for i in range(2019)] for j in range(2019)]
  ans = 2018
  m = 2019
  for i in range(l, r + 1):
    for j in range(i + 1, r + 1):
      ans = min(ans, LUT[i % m][j % m])
      if ans == 0:
        return 0
  return ans

print(main())
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
pp = [0]*n
for i in range(n):
  pp[i] = p[i]*(p[i]+1)/(2*p[i])

ans = 0
for i in range(n-k+1):
    tmp = sum(pp[i:i+k])
    if ans < tmp:
        ans = tmp
print(ans)

### FIXED CODE ###

import numpy as np

def dice():
    n, k = map(int, input().split())
    p = np.asarray(list(map(int, input().split())))
    pp = np.zeros(n)
    for i in range(n):
      pp[i] = p[i]*(p[i]+1)/(2*p[i])
    ans = sum(pp[0:k]) 
    tmp = sum(pp[0:k])
    for i in range(1, n-k+1):
        tmp = tmp - pp[i-1] + pp[i+k-1]
        if ans < tmp:
            ans = tmp
    print(ans)

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

import copy
from collections import deque

n = int(input())

ans = 0
array = ['7','5','3']

count = 0
d = deque()
d.append(([],set()))

while len(d) != 0:
  s,used = d.pop()
  if len(s) != 0 and int(''.join(s)) > n:
    continue
  
  if len(used) == 3:
    count += 1
    
  for c in array:
    cp_s = copy.deepcopy(s)
    cp_used = copy.deepcopy(used)
    cp_s.append(c)
    cp_used.add(c)
    d.append((cp_s,cp_used))
  
print(count)


### FIXED CODE ###

import copy
from collections import deque

n = int(input())

ans = 0
array = ['7','5','3']

count = 0
d = deque()
d.append(([],set()))

while len(d) != 0:
  s,used = d.pop()
  if len(s) != 0 and int(''.join(s)) > n:
    continue
  
  if len(used) == 3:
    count += 1  
    
  for c in array:
    cp_s = copy.deepcopy(s)
    cp_s.append(c)    
    if len(used) == 3:
      d.append((cp_s,used))
    
    else:
      cp_used = copy.deepcopy(used)
      cp_used.add(c)
      d.append((cp_s,cp_used))
  
print(count)
### BUGGY CODE ###

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

dp=[0]*N

for i in range(1,N):
    dp[i] = min(
        dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i)
    )

print(dp[N-1])

### FIXED CODE ###

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

    dp=[0]*N

    for i in range(1,N):
        dp[i] = min(
            dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i)
        )
    print(dp[N-1])
main()
### BUGGY CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for i in range(n-1,-1,-1):
    try:
        while p<n:
            if a[i]+a[p]<=md: p+=1
            else: break
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)


### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
### BUGGY CODE ###

import collections

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    s = input()
    a = []
    for j in range(w):
        a.append(s[j])
    maze.append(a)
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            ne = collections.deque()
            dist = [[0]*w for k in range(h)]
            checked = [[0]*w for k in range(h)]
            ne.append([i,j])
            while len(ne) != 0:
                cur = ne.popleft()
                checked[cur[0]][cur[1]] = 1
                for l in range(4):
                    t = cur[0]+dy_dx[l][0]
                    u = cur[1]+dy_dx[l][1]
                    if (0 <= t <= h-1) and (0 <= u <= w-1):
                        if checked[t][u] == 0:
                            if maze[t][u] == '.':
                                dist[t][u] = dist[cur[0]][cur[1]]+1
                                ne.append([t,u])
                                ans = max(ans,dist[t][u])
print(ans)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    maze.append(input())
flag = True
check = '.'*w
for i in range(h):
    if maze[i] != check:
        flag = False
        break
if flag:
    print(h+w-2)
else:
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                ne = deque([[i,j]])
                dist = [[0]*w for k in range(h)]
                checked = [[0]*w for k in range(h)]
                while len(ne) != 0:
                    cur = ne.popleft()
                    checked[cur[0]][cur[1]] = 1
                    for l in range(4):
                        t = cur[0]+dy_dx[l][0]
                        u = cur[1]+dy_dx[l][1]
                        if (0 <= t <= h-1) and (0 <= u <= w-1):
                            if checked[t][u] == 0:
                                if maze[t][u] == '.':
                                    dist[t][u] = dist[cur[0]][cur[1]]+1
                                    ne.append([t,u])
                                    ans = max(ans,dist[t][u])
    print(ans)
### BUGGY CODE ###

N = int(input())
A = []
while 1:
    A.append(N%10)
    N = N//10
    if N <= 0:
        break

if sum(A)%9==0:print("Yes")
else:print("No")

### FIXED CODE ###

A = list(input())
for n in range(len(A)):
    A[n] = int(A[n])

if sum(A)%9==0:print("Yes")
else:print("No")
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
l = [0]*Q
r = [0]*Q
for q in range(Q):
    l[q],r[q] = map(int,input().split())

for q in range(Q):
    cnt = 0
    for i in range((l[q]-1),r[q]-1):
        if S[i:i+2] == 'AC':
            cnt +=1
    print(cnt)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()

cnt = [0]*(N+1)
for i in range(N):
    if S[i:i+2] == 'AC':
        cnt[i+1] = cnt[i]+1
    else:
        cnt[i+1] = cnt[i]
    
#print(cnt)

for q in range(Q):
    l,r = map(int,input().split())
    print(cnt[r-1]-cnt[l-1])
### BUGGY CODE ###

n=int(input())
A=[]
for index in range(n):
    A.append(list(map(int,input().split())))

def warshall_floyd(G):
    h=len(G)

    res=0
    for x in range(h):
        for y in range(x+1,h):
            res+=G[x][y]

    check=[[0]*h for z in range(h)]
    for k in range(h):
        for i in range(h):
            for j in range(h):
                temp=G[i][k]+G[k][j]
                if temp==G[i][j]:
                   if i!=j and j!=k and k!=i:
                       check[i][j]=1
                elif temp<G[i][j]:
                    if i!=j and j!=k and k!=i:
                        check[i][j]=-1
    decrease=0             
    for p in range(h):
        for q in range(h):
            if check[p][q]==-1:
                return [False]
            elif check[p][q]==1:
                decrease+=G[p][q]
    else:
        return [True,res-decrease//2]


ans=warshall_floyd(A)
if not ans[0]:
    print(-1)
else:
    print(ans[1])



### FIXED CODE ###

n=int(input())
A=[]
for index in range(n):
    A.append(list(map(int,input().split())))

def warshall_floyd(G):
    h=len(G)

    res=0
    for x in range(h):
        for y in range(x+1,h):
            res+=G[x][y]

    check=[[0]*h for z in range(h)]
    for k in range(h):
        for i in range(h):
            for j in range(h):
                temp=G[i][k]+G[k][j]
                if temp==G[i][j]:
                   if i!=j and j!=k and k!=i:
                       check[i][j]=1
                elif temp<G[i][j]:
                    if i!=j and j!=k and k!=i:
                        check[i][j]=-1
    decrease=0             
    for p in range(h):
        for q in range(h):
            if check[p][q]==-1:
                return [False]
            elif check[p][q]==1:
                decrease+=G[p][q]
    else:
        return [True,res-decrease//2]


ans=warshall_floyd(A)
if not ans[0]:
    print(-1)
else:
    print(ans[1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
I = input()

R = I.count('R')
G = I.count('G')
B = I.count('B')

sum = R * G * B

for i in range(N):
    for j in range(i+1,N):
        if I[i] != I[j]:
            k = j + j - i
            if k >= N:
                continue
            if I[i] != I[k] and I[j] != I[k]:
                sum -= 1

print(sum)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
I = input()

R =0
G =0
B =0
for i in range(N):
    if (I[i] == 'R'):
        R+=1
    if (I[i] == 'G'):
        G+=1
    if (I[i] == 'B'):
        B+=1


sum = R * G * B

for i in range(N):
    for j in range(i+1,N):
        if I[i] != I[j]:
            k = j + j - i
            if k >= N:
                continue
            if I[i] != I[k] and I[j] != I[k]:
                sum -= 1

print(sum)
### BUGGY CODE ###

#salmonize の文
n,k = map(int,input().split()) 
 #複数文字の入力
ans = 0     
for i in range(n+1):
  j=0
  #カウンター設置
  while i<k:
    i*=2
    j+=1
  ans=1/2**j
print("{:.12}".format(ans/n))

### FIXED CODE ###

n,k = map(int,input().split()) 
 #複数文字の入力
ans = 0

for i in range(1,n+1):
  j=0 
  #カウンター設置
  while i<k:
    i*=2
    j+=1
  ans+=1/2**j
print("{:.12}".format(ans/n))
### BUGGY CODE ###

import math

k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            a = math.gcd(i,j)
            b = math.gcd(a,l)
            ans += b
print(ans)

### FIXED CODE ###

import math

k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        a = math.gcd(i,j)
        for l in range(1,k+1):
            b = math.gcd(a,l)
            ans += b
print(ans)
### BUGGY CODE ###


volume = [1,2,4, 8]
value = tuple(map(int, input().split()))
N = int(input())
 
counts = [10**10 for _ in range(N*4 + 1)]
counts[0] = 0
 
for i in range(4):
    for n in range(volume[i], N*4+1):
        counts[n] = min(counts[n], counts[n-volume[i]] + value[i])
 
print(counts[-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

volume = [1, 2, 4, 8]
value = {k:v for k, v in zip(volume, inpl())}
cosp = {k:v/k for k, v in value.items()}
N = int(input())
N = N*4
res = 0

for k, _ in sorted(cosp.items(), key=lambda x: x[1]):
    res += (N // k)*value[k]
    N = N % k
print(int(res))
### BUGGY CODE ###

# A
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

N, M = list(map(int, input().split()))
S = input()
T = input()

re = -1
# 1文字目が必ず一緒であること
if S[0] == T[0]:
    min_num = (N * M)  // gcd(N, M) # 最小公倍数を求める（基本はこれが答え）
    re = min_num
    # 重なる部分が同じ文字かを調べる
    s_d = min_num // N
    t_d = min_num // M
    # 最小公倍数みる
    st_min = (s_d * t_d) // gcd(s_d, t_d)
    st = st_min
    while st < N and st < M:
        if S[st // (min_num // N)] != T[st // (min_num // M)]:
            re = -1
            break

print(re)


### FIXED CODE ###

# A
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

N, M = list(map(int, input().split()))
S = input()
T = input()

re = -1
if S == T:
    re = N
elif S[0] == T[0]:
    min_num = (N * M)  // gcd(N, M) # 最小公倍数を求める（基本はこれが答え）
    re = min_num
    # 重なる部分が同じ文字かを調べる
    s_d = min_num // N
    t_d = min_num // M
    # 最小公倍数みる
    st_min = (s_d * t_d) // gcd(s_d, t_d)
    st = st_min
    i = 1
    while st // s_d < N and st // t_d < M:
        if S[st // s_d] != T[st // t_d]:
            re = -1
            break
        else:
            i += 1
            st = st_min * i

print(re)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


mod = 998244353
N = int(input())
A = [int(input()) for _ in range(N)]

S = sum(A)
L = S//2
dp1 = [0]*(L+1)
dp2 = [0]*(L+1)
dp1[0] = 1
dp2[0] = 1
for a in A:
    for i in reversed(range(L-a+1)):
        dp1[i+a] = (dp1[i+a] + dp1[i])%mod
        dp2[i+a] = (dp2[i+a] + dp2[i]*2)%mod

p1 = 0
p2 = 0
for s in range(1,L+1):
    p1 = (p1 + dp1[s]*6)%mod
    p2 = (p2 + dp2[s]*3)%mod
ans = (pow(3, N, mod) + 3 - 3*pow(2, N, mod) - p2 + p1) % mod
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline


mod = 998244353
N = int(input())
A = [int(input()) for _ in range(N)]

S = sum(A)
L = S//2
dp1 = [0]*(L+1)
dp2 = [0]*(L+1)
dp1[0] = 1
dp2[0] = 1
for a in A:
    for i in reversed(range(L-a+1)):
        dp1[i+a] = (dp1[i+a] + dp1[i])%mod
        dp2[i+a] = (dp2[i+a] + dp2[i]*2)%mod

p1 = 0
p2 = 0
for s in range(1,L+1):
    p1 = (p1 + dp1[s]*6)%mod
    p2 = (p2 + dp2[s]*3)%mod
ans = (pow(3, N, mod) + 3 - 3*pow(2, N, mod) - p2 + p1) % mod
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

l = {}

for a in A:
    if a in l.keys():
        l[a] += 1
    else:
        l[a] = 1

from functools import lru_cache
# @lru_cache(maxsize=None)
# def divisor(n):
#     i = 1
#     table = []
#     while i * i <= n:
#         if n % i == 0:
#             table.append(i)
#             table.append(n // i)
#         i += 1
#     table = list(set(table))
#     return table

@lru_cache(maxsize=None)
def mySolve(n):
    flag = True
    i = 1
    while i * i <= n:
        if n % i == 0:
            d = i
            if d != a:
                if d in l.keys():
                    flag = False
                    break
            elif l[d] >= 2:
                flag = False
                break
            d = n//i
            if d != a:
                if d in l.keys():
                    flag = False
                    break
            elif l[d] >= 2:
                flag = False
                break
        i += 1
    return flag

# @lru_cache(maxsize=None)
# def mySolve(n):
#     flag = True
#     da = divisor(a)
#     for d in da:
#         if d != a:
#             if d in l.keys():
#                 flag = False
#                 break
#         elif l[d] >= 2:
#             flag = False
#             break
#     return flag

ans = 0
for a in A:
    if mySolve(a):
        ans += 1

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

l = [0]*1000001

A.sort()

for a in A:
    if l[a] == 0:
        l[a] = 1
        tmp = 2
        while tmp*a <= 1000000:
            l[tmp*a] = 2
            tmp+=1
    elif l[a] == 1:
        l[a] = 2

ans = 0
for a in A:
    if l[a] != 2:
        ans += 1

print(ans)