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

import heapq

N, M = [int(x) for x in input().split()]
A = list([int(x) * - 1 for x in input().split()])

while M > 0:
    heapq.heapify(A)
    count = (heapq.heappop(A) * -1 // 2) * -1

    heapq.heappush(A, count)
    M -= 1

print(sum(A) * -1)


### FIXED CODE ###

import heapq

N, M = [int(x) for x in input().split()]
A = list([int(x) * - 1 for x in input().split()])
heapq.heapify(A)

for _ in range(M):
    target = heapq.heappop(A) * -1
    heapq.heappush(A, (target // 2) * -1)

print(sum(A) * -1)
### BUGGY CODE ###

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

pos = []
for i in range(Q):
    pos.append(list(map(int, input().split())))
    
def countAC(S, r, l):
    data = S[r-1:l]
    cnt = 0
    for i in range(len(data)-1):
        if data[i]=='A':
            if data[i+1] == 'C':
                cnt+=1
    return cnt
  
ret = []
for it in pos:
    cnt = countAC(S, it[0], it[1])
    ret.append(str(cnt))
print('\n'.join(ret))

### FIXED CODE ###

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

cumul = [0]*len(S)
cnt = 0
for i in range(len(S)-1):
    cumul[i] = cnt
    if S[i]=='A':
        if S[i+1] == 'C':
            cnt+=1
cumul[-1]=cnt

ret = []
for i in range(Q):
    l, r = map(int, input().split())
    cnt = cumul[r-1] - cumul[l-1]
    ret.append(str(cnt))
print('\n'.join(ret))
### BUGGY CODE ###

wi,vi = 0, 1
N,W = map(int, input().split())

nupList = [list(map(int, input().split())) for _ in range(N)]

dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(N):

    v = nupList[i][vi]
    w = nupList[i][wi]
    for j in range(W + 1):
        if j < w:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + v)

print(dp[N][W])

### FIXED CODE ###

def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)
 
    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())
### BUGGY CODE ###

N,M=map(int,input().split())
scan=[]
gcan=[]
flag=0
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        scan.append(b)
    if b==N:
        gcan.append(a)
for i in scan:
    for j in gcan:
        if i==j:
            flag=1
            break
    if flag==1:
        break
if flag==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

N,M=map(int,input().split())
scan=[]
gcan=[]
flag=0
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        scan.append(b)
    if b==N:
        gcan.append(a)
if set(scan)&set(gcan):
    flag=1
if flag==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

def main():
	L = input()
	n = len(L)
	MOD = 10**9+7
	ans = 0
	times = 1
	if n > 1:
		ans = (3**(n-1))
		times = 2
		ans %= MOD

	cur = 1
	if L[n-1] == "1":
		cur = 3

	for i in range(n-2, 0, -1):
		if L[i] == "1":
			cur <<= 1
			cur %= MOD
			cur += (3**(n-i-1))%MOD
			cur %= MOD
	cur *= times
	cur %= MOD
	ans += cur
	ans %= MOD
	print(ans)


if __name__ == '__main__':
	main()

### FIXED CODE ###

MOD = 10**9+7

memo = dict()
memo[0] = 1
def pow3(n):
	if n in memo:
		return memo[n]
	if n%2 == 0:
		tmp = pow3(n//2)
		memo[n] = tmp*tmp%MOD
		return memo[n]
	memo[n] = 3 * pow3(n-1)%MOD
	return memo[n]

def cul(i, p):
	cur = (1<<i)%MOD
	cur *= pow3(p)
	return cur % MOD

def solve(L):
	n = len(L)
	if L == "0":
		return 1
	if not "0" in L:
		return pow3(n)

	num_1 = 0
	pos = []
	for i in range(n):
		if L[i] == "1":
			num_1 += 1
			pos.append(n-i-1)

	ans = (2**num_1)%MOD
	for i, p in enumerate(pos):
		ans += cul(i, p)
		ans %= MOD

	return ans

def main():
	L = input()
	print(solve(L))


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

mod = 998244353
N, K = map(int,input().split())

v = []
for _ in range(K):
    L, R = map(int,input().split())
    # for d in range(L, R+1):
    #     moves.append(d)
    v.append((L, R))
v.sort()

dp = [0] * N        # マスi-1に到達するまでの操作列の個数
sdp = [0] * (N + 1) # dp[i]までの累積和 
dp[0] = 1
sdp[1] = 1

for n in range(1, N):
    for p in v:
        left = max(0, n - p[1])
        right = max(0, n - p[0]+1)
        dp[n] += sdp[right] - sdp[left]
    sdp[n+1] = sdp[n] + dp[n]

print(dp[-1] % mod)

### FIXED CODE ###

n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])
### BUGGY CODE ###

import math
N = input()
A = input().split()
N = int(N)
sum = 1
for i in range(N):
    sum *= int(A[i])
if sum > 1000000000000000000:
    sum = -1
print(sum)

### FIXED CODE ###

N = input()
A = input().split()
if '0' in A:
    print(0)
else:
    N = int(N)
    sum = 1
    for i in range(N):
        sum *= int(A[i])
        if sum > 10**18:
            print(-1)
            exit()
    print(sum)
### BUGGY CODE ###

n=int(input())
A=[]
for i in range(0,n):
    A.append(int(input()))
for j in range(0,n):
    s=A[j]
    A.pop(j)
    print(max(A))
    A.insert(j,s)

### FIXED CODE ###

import copy
from sys import stdin
n=int(input())
A=[int(stdin.readline().rstrip()) for _ in range(n)]
z=max(A)
B=sorted(A)
o=B[n-2]
for j in range(0,n):
    if A[j]<z:
       print(z)
    else:
        if B[n-2]==B[n-1]:
           print(z)
        else:
           print(o)
### BUGGY CODE ###

#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

#input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


h , w = map(int , input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch-=1
cw-=1
dh-=1
dw-=1
arr = [list(input()) for i in range(h)]
#print(arr)
can_vis = []
dist = [[float("inf")]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw,0))
dist[ch][cw] = 0
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury,magic = q.popleft()
	#can_vis.append((curx,cury))
	f = 0
	if curx == dh and cury == dw:
		ans = min(ans, magic)
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.append((curx+dx, cury+dy,magic))
			f = 1
	if f: continue
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy,magic+1))


if dist[dh][dw] == float("inf"):
	print(-1)
else:
	print(dist[dh][dw])



### FIXED CODE ###

#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


h , w = map(int , input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch-=1
cw-=1
dh-=1
dw-=1
arr = [input() for i in range(h)]
#print(arr)
can_vis = []
dist = [[10**10]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw))
dist[ch][cw] = 0
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury = q.popleft()
	#can_vis.append((curx,cury))
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.appendleft((curx+dx, cury+dy))
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury] + 1:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy))


if dist[dh][dw] == 10**10:
	print(-1)
else:
	print(dist[dh][dw])
### BUGGY CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
a = []
for i in range(Q):
    a.append(map(int, raw_input().split()))
for i,temp in enumerate(a):
    if i == 0:
        result = str(string[temp[0]-1:temp[1]].count('AC'))
    else:
        result += '\n' + str(string[temp[0]-1:temp[1]].count('AC'))
print(result)

### FIXED CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
cnt = [0]
for i in range(N):
#    print(i)
#    print(string[i-2:i])
#    if i == 0:
#        cnt.append(0)
#        continue
    if string[i-1:i+1] == 'AC':
        cnt.append(cnt[i]+1)
        continue
    cnt.append(cnt[i])

for j in range(Q):
    #print(j)
    pare = map(int, raw_input().split())
    print(cnt[pare[1]] - cnt[pare[0]])
### BUGGY CODE ###

# E

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

def gcd(a,b):
    if a>b:
        a,b=b,a
    while a%b:
        a,b=b,(a%b)
    return b

def fast_factorization_init(N):
    res=list(range(N))
    for i in range(2,N):
        if i*i>N:
            break
        for j in range(i*i,N,i):
            if res[j]==j:
                res[j]=i
        if res[i]<i:
            continue
    return res            
    
min_factors=fast_factorization_init(10**6+10)
def fast_factorization(n):
    res=[]
    while n>1:
        res.append(min_factors[n])
        n//=min_factors[n]
    return res

res2=1
P=[]
for i in range(N):
    if i!=0:
        res1=gcd(A[i],res1)
    else:
        res1=A[0]
    fact=fast_factorization(A[i])
    if res2!=0:
        for p in P:
            if A[i]%p==0:
                res2=0
                break
    for p in fact:
        P.append(p)
if res2==1:
    print('pairwise coprime')
elif res1==1:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

# E

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

def gcd(a,b):
    if a>b:
        a,b=b,a
    while a%b:
        a,b=b,(a%b)
    return b

def fast_factorization_init(N):
    res=list(range(N))
    for i in range(2,N):
        if i*i>N:
            break
        for j in range(i*i,N,i):
            if res[j]==j:
                res[j]=i
        if res[i]<i:
            continue
    return res            
    
min_factors=fast_factorization_init(10**6+10)
def fast_factorization(n):
    res=[]
    while n>1:
        res.append(min_factors[n])
        n//=min_factors[n]
    return list(set(res))

res2=0
P=[]
for i in range(N):
    if i!=0:
        res1=gcd(A[i],res1)
    else:
        res1=A[0]
    P += fast_factorization(A[i])

if len(set(P))==len(P):
    res2=1

if res2==1:
    print('pairwise coprime')
elif res1==1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

import collections

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

path = [[False for i in range(N)] for j in range(N)]
detect_start = [[False for i in range(N)] for j in range(N)]
for i in range(M) :
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    detect_start[b][a] = True

start = []
for i in range(N) :
    for j in range(N) :
        if detect_start[i][j] :
            break
    else :
        start.append(i)

ans = 0

for i in range(len(start)) :
    q = collections.deque()
    q.append(start[i])
    dist = [0 for i in range(N)]
    
    while q :
        now = q.popleft()
        for j in range(N) :
            if path[now][j] :
                q.append(j)
                dist[j] = max(dist[j], dist[now]+1)
    
    ans = max(ans, max(dist))

print(ans)


### FIXED CODE ###

N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]

L_minus = [[] for i in range(N)]
L_plus = [0 for i in range(N)]

dp = [0 for i in range(N)]

for i in range(M) :
    x,y = L[i]
    x -= 1
    y -= 1
    L_plus[y] += 1
    L_minus[x].append(y)

A = []

for i in range(N) :
    if L_plus[i] == 0 :
        A.append(i)

while A :
    x = A.pop()
    
    for y in L_minus[x] :
        L_plus[y] -= 1
        if L_plus[y] == 0 :
            A.append(y)
        dp[y] = max(dp[y], dp[x]+1)

ans = max(dp)

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

import numpy as np

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

#O(N)
def imos(x):
  global N
  B = np.zeros_like(x)
  for i in range(N):
    p = x[i]
    L = max(i-p, 0)
    R = min(i+p, N-1)
    B[L] += 1
    if R < N-1:
      B[R+1] -= 1
  B = np.cumsum(B)
  return B

for i in range(K):
  if i >= 50:
    break
  A = imos(A)

print(*A)

### FIXED CODE ###

import numpy as np

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

from numba import jit

@jit
def imos(x):
  global N
  B = np.zeros_like(x)
  for i in range(N):
    p = x[i]
    L = max(i-p, 0)
    R = min(i+p, N-1)
    B[L] += 1
    if R < N-1:
      B[R+1] -= 1
  B = np.cumsum(B)
  return B

for i in range(K):
  if i >= 50:
    break
  A = imos(A)

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

#! /usr/bin/env python3

n, m = map(int, input().split())
a = [int(i) for i in input().split()]

acc = 0
res = 0

mods = {}

for i in range(n):
    acc = (acc + a[i]) % m

    if acc == 0:
         res += 1

    for k, v in mods.items():
        if acc == k:
            res += v

    if acc in mods:
        mods[acc] += 1
    else:
        mods[acc] = 1

print(res)


### FIXED CODE ###

#! /usr/bin/env python3

n, m = map(int, input().split())
a = [int(i) for i in input().split()]

acc = 0
res = 0

mods = {}

for i in range(n):
    acc = (acc + a[i]) % m

    if acc == 0:
         res += 1

    if acc in mods:
        res += mods[acc]
        mods[acc] += 1
    else:
        mods[acc] = 1

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

def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque
n,m=LI()
edge=[[]*n for i in range(n)]
for i in range(m):
    a,b=LI()
    a-=1;b-=1
    edge[a].append(b)
    edge[b].append(a)

ans=[-1]*n
goal=deque([0])
while (-1 in ans):
    g=goal.popleft()
    for i,v in enumerate(edge):
        if v==-1:continue
        if g in v:
            ans[i]=g+1
            edge[i]=-1
            goal.append(i)

if (-1 in ans):
    no()
    exit()
yes()
for i in ans[1:]:
    print(i)



### FIXED CODE ###

def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque

def main():
    n,m=LI()
    edge=[[] for i in range(n)]
    for i in range(m):
        a,b=LI()
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)    
    ans=[-1]*(n)
    goal=deque([0])
    while goal:
        g=goal.popleft()
        for i in edge[g]:
            if ans[i]==-1:
                ans[i]=g+1
                goal.append(i)
    yes()
    print(*ans[1:])
main()
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
  dp[1]=0
else:
  dp[1]=1
for i in range(2,n+1):
  if i in a:
    dp[i]=0
  else:
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)


### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
mod=1000000007
dp=[1,1]
if 1 in a:
  dp[1]=0
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append((dp[-1]+dp[-2])%mod)
print(dp[-1]%mod)
### BUGGY CODE ###

# 組み合わせの数を出力
n = int(input())
s = [sorted(input()) for _ in range(n)]
t = 0
dup = []
# sが空っぽになるまで重複するものを消して差分を控える
while s:
    t = len(s)
    pop = s.pop()
    try:
        while True:
            s.remove(pop)
    except ValueError:
        pass
    dup.append(t-len(s))

ans = sum(c*(c-1)//2 for c in dup)
print(ans)


### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
dup = collections.Counter(s).values()

ans = sum(c*(c-1)//2 for c in dup)
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
ST = [[row[w] for row in S] for w in range(W)]
count_matw = [[0 for w in range(W)]for h in range(H)]
count_math = [[0 for w in range(W)]for h in range(H)]

for h in range(H):
    row = S[h]
    for w in range(W):
        if w > 0 and row[w] != '#' and count_matw[h][w-1] != 0:
            count_matw[h][w] = count_matw[h][w-1]
            continue
        if '#' in row[w:]:
            obs_i = row[w:].index('#')
            count_matw[h][w] = obs_i
        else:
            count_matw[h][w] = W-w
for w in range(W):
    col = ST[w]
    for h in range(H):
        if h > 0 and col[h] != '#' and count_math[h-1][w] != 0:
            count_math[h][w] = count_math[h-1][w]
            continue
        if '#' in col[h:]:
            obs_i = col[h:].index('#')
            count_math[h][w] = obs_i
        else:
            count_math[h][w] = H-h
ans = max([count_math[h][w] + count_matw[h][w]for h in range(H) for w in range(W)])
print(ans-1)


### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
count_matw = [[0 for w in range(W)]for h in range(H)]
count_math = [[0 for w in range(W)]for h in range(H)]

for h in range(H):
    count = 0
    for w in range(W):
        if '#' == S[h][w]:
            count = 0
        else:
            count += 1
        count_matw[h][w] = count
    for w in range(W-1, 0, -1):
        if count_matw[h][w-1] == 0:
            continue
        count_matw[h][w-1] = max(count_matw[h][w], count_matw[h][w-1])

for w in range(W):
    count = 0
    for h in range(H):
        if '#' == S[h][w]:
            count = 0
        else:
            count += 1
        count_math[h][w] = count
    for h in range(H-1, 0, -1):
        if count_math[h-1][w] == 0:
            continue
        count_math[h-1][w] = max(count_math[h][w], count_math[h-1][w])
ans = 1
# for h in range(H):
#     for w in range(W):
#         ans = max(ans, count_math[h][w] + count_matw[h][w])
ans = max([count_math[h][w] + count_matw[h][w] for h in range(H) for w in range(W)])
# print(count_math)
# print(count_matw)
print(ans-1)
### BUGGY CODE ###

N, K = map(int,input().split()) 
P = list(map(int,input().split()))
max_index = 0
max_size = 0
for i in range(N-K+1):
    sum_3 = sum(P[i:i+K])
    if sum_3 > max_size:
        max_index = i
        max_size = sum_3
expect = 0
for j in range(K):
    X = P[max_index+j]
    expect += (X+1)*X/(2*X)
print(expect)

### FIXED CODE ###

def expect(n):
    return (int(n)+1)/2
N, K = map(int,input().split()) 
P = list(map(expect,input().split()))
sumlist = [sum(P[0:K])]
sumnumber = sum(P[0:K])
for i in range(N-K):
    sumnumber -=P[i]
    sumnumber +=P[i+K]
    sumlist.append(sumnumber)
print(max(sumlist))
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(a, b+1):
  if min(i-a+1, b-i+1) <= k:
    print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
s, l = [], []
for i in range(k):
  if a+i == b-i:
    s.append(a+i)
    break
  else:
    s.append(a+i)
    l.append(b-i)
    if b-a-2*i == 1:
      break
for i in s:
  print(i)
for i in l[::-1]:
  print(i)
### BUGGY CODE ###

A,B = map(int,input().split())
import math
def cf(x1,x2):
    l=[]
    min_x = min(x1,x2)
    for i in range(2,math.ceil(min_x/2)+1):
        if x1 % i == 0 and x2 % i == 0:
            l.append(i)
    return l


def is_prime(n):
    if n == 1:
      return False
    elif n==2:
      True
    elif n%2==0:
      False

    for k in range(3, int(math.sqrt(n)) + 1,2):
        if n % k == 0:
            return False

    return True

cf_l = cf(A,B)
answer = 0
while cf_l:
  cf_0 = cf_l[0]
  cf_l = cf_l[1::]
  if is_prime(cf_0):
    answer += 1
    cf_l = list(filter(lambda x:x%cf_0!=0,cf_l))
print(answer+1)

### FIXED CODE ###

A,B = map(int,input().split())
import math
import fractions
def factorization(n):
    arr = []
    temp = n
    if n!=1:
      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 len(arr)
    else:
      return 0
print(factorization(fractions.gcd(A,B))+1)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=set(A)
A.sort()
ans=[1]*max(A)
for i in range(len(A)):
  if ans[A[i]-1]!=0:
    if i>0 and A[i]==A[i-1]:
      ans[A[i]-1]=0
    for j in range(A[i]*2,max(A)+1,A[i]):
      ans[j-1]=0
k=0
for i in A:
  if ans[i-1]==1:
    k+=1
print(k)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=set(A)
A.sort()
S=max(A)
ans=[1]*S
for i in range(len(A)):
  if ans[A[i]-1]!=0:
    if i>0 and A[i]==A[i-1]:
      ans[A[i]-1]=0
    for j in range(A[i]*2,S+1,A[i]):
      ans[j-1]=0
k=0
for i in A:
  if ans[i-1]==1:
    k+=1
print(k)
### BUGGY CODE ###

import itertools
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
l = IL()
setl = list(set(l))

ans = 0
if len(l) == 0:
	pass
else:
	for i in range(len(setl)):
		tmp = l.count(setl[i])
		if tmp < setl[i]:
			ans += tmp
		else:
			ans += tmp-setl[i]

print(ans)

### FIXED CODE ###

import collections
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
l = IL()
cl = collections.Counter(l)

key = list(cl.keys())
value = list(cl.values())

ans = 0
for i in range(len(key)):
	k = int(key[i])
	v = value[i]
	if k <= v:
		ans += v-k
	else:
		ans += v

print(ans)