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

import numpy as np

def main():
    n = int(input())
    a = np.zeros([n], dtype=int)
    box = np.array(range(1,n+1))
    a = list(map(int, input().split(" ")))
    b = np.zeros_like(a)

    for i in range(n//2, n):
        if a[i] == 1:
            b[i] = 1

    for i in box[:n//2][::-1]:
        if np.sum(b[i-1::i])%2 != a[i-1]:
            b[i-1] = 1

    ball = np.where(b==1)[0]
    print(len(ball))
    for i in ball:
        print(box[i], end=" ")
        

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np

def main():
    n = int(input())
    a = np.zeros([n], dtype=int)
    # box = np.array(range(1,n+1))
    a = list(map(int, input().split(" ")))
    b = np.zeros_like(a)

    for i in range(n//2, n):
        if a[i] == 1:
            b[i] = 1

    for i in range(1,n//2+1)[::-1]:
        if np.sum(b[i-1::i])%2 != a[i-1]:
            b[i-1] = 1

    ball = np.where(b==1)[0]
    print(len(ball))
    for i in ball:
        print(i+1, end=" ")
        
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, M, L = map(int, input().split())
dp = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
for i in range(N):
    dp[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#print('distance={}'.format(dp))


dp2 = [[float('inf')] * N for _ in range(N)]
for a in range(N - 1):
    for b in range(a+1, N):
        if dp[a][b] <= L:
            dp2[a][b] = 1
            dp2[b][a] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j])
#print('times={}'.format(dp2))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if dp2[s-1][t-1] != float('inf'):
        print(dp2[s-1][t-1] - 1)
    else:
        print(-1)


### FIXED CODE ###

inf = 10 ** 15

N, M, L = map(int, input().split())
dp = [[inf] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
for i in range(N):
    dp[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#print('distance={}'.format(dp))


dp2 = [[inf] * N for _ in range(N)]
for a in range(N - 1):
    for b in range(a+1, N):
        if dp[a][b] <= L:
            dp2[a][b] = 1
            dp2[b][a] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j])
#print('times={}'.format(dp2))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    cost = dp2[s-1][t-1]
    if cost != inf:
        print(cost - 1)
    else:
        print(-1)
### BUGGY CODE ###

n = int(input())
slist = []
for i in range(n):
    slist.append(input())

first_list = []
last_list = []
for i in range(n):
    s = slist[i]

    a_count = 0
    b_count = 0
    min_s = ""
    for c in s:
        if c == ")":
            b_count-=1
        else:
            b_count+=1
        if b_count < 0:
            b_count = 0
            a_count+= 1
    min_s = ")"* a_count + "("*b_count

    ai = a_count
    bi = b_count
    if bi-ai >= 0:
        first_list.append([min_s,ai])
    else:
        last_list.append([min_s,bi])

first_list= sorted(first_list, key=lambda s: s[1])
last_list= sorted(last_list, key=lambda s: s[1], reverse=True)

ans = ""
for i in range(len(first_list)):
    ans += first_list[i][0]
for i in range(len(last_list)):
    ans += last_list[i][0]

a_count = 0
b_count = 0
min_s = ""
for c in ans:
    if c == ")":
        b_count-=1
    else:
        b_count+=1
    if b_count < 0:
        b_count = 0
        a_count+= 1

if a_count == 0 and b_count == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
slist = []
for i in range(n):
    slist.append(input())

first_list = []
last_list = []
first = ""
last = ""
for i in range(n):
    s = slist[i]

    a_count = 0
    b_count = 0
    min_s = ""
    for c in s:
        if c == ")":
            b_count-=1
        else:
            b_count+=1
        if b_count < 0:
            b_count = 0
            a_count+= 1
    min_s = ")"* a_count + "("*b_count

    ai = a_count
    bi = b_count

    if ai == 0:
        first += min_s
    elif bi == 0:
        last += min_s
    elif bi-ai >= 0:
        first_list.append([min_s,ai])
    else:
        last_list.append([min_s,bi])

first_list= sorted(first_list, key=lambda s: s[1])
last_list= sorted(last_list, key=lambda s: s[1], reverse=True)

ans = first
for i in range(len(first_list)):
    ans += first_list[i][0]
for i in range(len(last_list)):
    ans += last_list[i][0]
ans += last

a_count = 0
b_count = 0
min_s = ""
for c in ans:
    if c == ")":
        b_count-=1
    else:
        b_count+=1
    if b_count < 0:
        b_count = 0
        a_count+= 1

if a_count == 0 and b_count == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n,k = map(int,input().split())
sl = [0]*n
dl = [0]*n
tree = [[] for i in range(n)]
mod = 10**9+7

for i in range(n-1):
  a,b = map(int,input().split())
  tree[a-1] += [b-1]
  tree[b-1] += [a-1]

def perm(n, k = 1):
  pdt = 1
  
  if n != int(n) or k != int(k):
    raise ValueError("perm() not defined for float object")
  
  elif k < 0:
    pdt = 0
  
  elif n < 0:
    pdt = 0
  
  else:
    for x in range(n, n-k, -1):
      pdt *= x
      
  return pdt

def dfs(x,depth,k):
  sl[x] = 1
  dl[depth] += 1
  child = 0
  ans = 1
  for i in tree[x]:
    if sl[i] == 0:
      ans *= dfs(i,depth+1,k)
      ans %= mod
      child += 1
  if depth == 0:
    ans *= perm(k-1,child)
    ans %= mod
  else:    
    ans *= perm(k-2,child)
    ans %= mod
  return ans

print(dfs(0,0,k)*k%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
mod = 10**9+7

def main():
  
  n,k = map(int,input().split())
  sl = [0]*(n+1)
  tree = [[] for i in range(n+1)]
  
  for i in range(n-1):
    a,b = map(int,input().split())
    tree[a] += (b,)
    tree[b] += (a,)

  def dfs(x,depth,k):
    sl[x] = 1
    child = 0
    ans = 1
    for i in tree[x]:
      if sl[i] == 0:
        ans *= dfs(i,depth+1,k)
        child += 1
    if depth == 0:
      for x in range(k-1, k-1-child, -1):
        ans = ans * x % mod   
    else:    
      for x in range(k-2, k-2-child, -1):
        ans = ans * x % mod
    ans %= mod
    return ans

  print(dfs(1,0,k)*k%mod)

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

from itertools import *
import sys
import numpy as np
md=10**9+7
mis=map(int,sys.stdin.readline().split())

h,w=mis
t=np.zeros((h+1,w+1),dtype="uint64")
t[1][1]=1
s=[]
for _ in range(h):
    s+=[input()]

for i,j in product(range(h),range(w)):
    if i==0 and j==0:continue
    if s[i][j]==".":
        t[i+1][j+1]=(t[i][j+1]+t[i+1][j])%md
    else:
        t[i+1][j+1]=0

print(t[-1][-1])


### FIXED CODE ###

from itertools import *
import sys
md=10**9+7
mis=map(int,sys.stdin.readline().split())

h,w=mis
t=[[0]*(w+1) for _ in range(h+1)]
s=[]
for _ in range(h):
    s+=[input()]

for i,j in product(range(h),range(w)):
    if i==0 and j==0:
        t[i+1][j+1]=1
    elif s[i][j]==".":
        t[i+1][j+1]=(t[i][j+1]+t[i+1][j])%md
    else:
        t[i+1][j+1]=0
print(t[-1][-1])
### BUGGY CODE ###

def solve():
    def max2(x, y): return x if x >= y else y
    def min2(x, y): return x if x <= y else y

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

    dp = [[0]*(N) for _ in range(N)]

    if N%2 == 1:
        for i, A in enumerate(As):
            dp[i][i] = A
    else:
        for i, A in enumerate(As):
            dp[i][i] = -A

    for W in range(2, N+1):
        if (N-W)%2 == 0:
            for L in range(N-W+1):
                R = L+W-1
                dp[L][R] = max2(As[L]+dp[L+1][R], As[R]+dp[L][R-1])
        else:
            for L in range(N-W+1):
                R = L+W-1
                dp[L][R] = min2(-As[L]+dp[L+1][R], -As[R]+dp[L][R-1])

    print(dp[0][N-1])


solve()


### FIXED CODE ###

def solve():
    def max2(x, y): return x if x >= y else y
    def min2(x, y): return x if x <= y else y

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

    dp = [[0]*(N) for _ in range(N)]

    if N%2 == 1:
        for i, A in enumerate(As):
            dp[i][i] = A
    else:
        for i, A in enumerate(As):
            dp[i][i] = -A

    for W in range(2, N+1):
        if (N-W)%2 == 0:
            for L in range(N-W+1):
                R = L+W-1
                dp[L][R] = max2(As[L]+dp[L+1][R], As[R]+dp[L][R-1])
        else:
            for L in range(N-W+1):
                R = L+W-1
                dp[L][R] = min2(-As[L]+dp[L+1][R], -As[R]+dp[L][R-1])

    print(dp[0][N-1])


solve()
### BUGGY CODE ###

h,w,m=[int(x) for x in input().split()]

hnm=[0]*h
wnm=[0]*w
bomb=[]
for _ in range(m):
    hi,wi=[int(x)-1 for x in input().split()]
    hnm[hi]+=1
    wnm[wi]+=1
    bomb.append((hi,wi))

sth=[[j,i] for i,j in enumerate(hnm)]
sth.sort(reverse=True)
stw=[[j,i] for i,j in enumerate(wnm)]
stw.sort(reverse=True)
    
hmax=-1
hidx=[]
for val,idx in sth:
    if hmax==-1:
        hmax=val
    elif hmax!=val:
        break
    hidx.append(idx)
    
wmax=-1
widx=[]
for val,idx in stw:
    if wmax==-1:
        wmax=val
    elif wmax!=val:
        break
    widx.append(idx)
    
ofst=-1
for i in hidx:
    for j in widx:
        if not (i,j) in bomb:
            ofst=0
            break
                
print(hmax+wmax+ofst)

### FIXED CODE ###

from collections import Counter
from collections import defaultdict
from heapq import heapify
from heapq import heappop
from heapq import heappush
from _collections import defaultdict

h,w,m=[int(x) for x in input().split()]

hcnt=defaultdict(int)
wcnt=defaultdict(int)
bomb=set()
for _ in range(m):
    hi,wi=[int(x)-1 for x in input().split()]
    hcnt[hi]+=1
    wcnt[wi]+=1
    bomb.add((hi,wi))

hmax=max(hcnt.values())
wmax=max(wcnt.values())

hidx=[x for x,y in hcnt.items() if y==hmax]
widx=[x for x,y in wcnt.items() if y==wmax]

ofst=-1
for i in hidx:
    for j in widx:
        if not (i,j) in bomb:
            ofst=0
            break
                
print(hmax+wmax+ofst)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**9)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n:
        return 1
    if r == 1:
        return n
    if (n,r) in nCr:
        return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

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

ans = 0
for i in range(N-K+1):
    ans += A[-1-i]*cmb(N-1-i, K-1)
    ans %= INF
    ans -= A[i]*cmb(N-1-i, K-1)
    ans %= INF

print(ans)

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

ans = 0
for i in range(N-K+1):
    ans += A[-1-i]*cmb(N-1-i, K-1, mod)
    ans %= mod
    ans -= A[i]*cmb(N-1-i, K-1, mod)
    ans %= mod

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

A, B, K = map(int, input().split())

ans = []
for i in range(A, B+1):
    if i <= A+K-1  or i >= B - K + 1:
        ans.append(i)
for j in ans:
    print(j)


### FIXED CODE ###

A, B, K = map(int, input().split())

k = K-1
if A+k >= B-k:
    for i in range(A, B+1):
        print(i)
else:
    for j in range(A, A+k+1):
        print(j)
    for k in range(B-k, B+1):
        print(k)
### BUGGY CODE ###

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

A_all = sum(As)//2

ans = []
for i in range(N):
    cnt = 0
    for j in range(N//2):
        index = i+2*j
        cnt += As[index%N]
    ans.append((A_all-cnt)*2)
 
a = ""
for i in range(1,N+1):
    a += str(ans[i%N])+" "
print(a)

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
A_all = sum(As)//2
ans = [0]*N

a0 = sum(As[1:N:2])
ans[0] = (A_all-a0)
for i in range(1,N):
    ans[i] = As[i-1]-ans[i-1]

ans = [a*2 for a in ans]
print(*ans)
### BUGGY CODE ###

k,s = map(int,input().split())
x = 0
for d in range(0,k+1):
    for y in range(0,k+1):
        z = s - d - y
        if d+y+z == s and z<k+1 and z>=0:
            x = x+1
print (x)
 

### FIXED CODE ###

k,s = map(int,input().split())
x = 0
for d in range(0,k+1):
    for y in range(0,k+1):
        z = s - d - y
        if z<k+1 and z>=0:
            x = x+1
print (x)
### BUGGY CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_b
# B - Frog 2

N,K=list(map(int,input().strip().split(' ')))
H=list(map(int,input().strip().split(' ')))



dp = [0] * N

for i in range(1, N):
    MIN = 10**9
    for j in range(1, K + 1):
        if i - j < 0:
            continue
        MIN = min(dp[i - j] + abs(H[i] - H[i - j]), MIN)
    dp[i] = MIN

print(dp[-1])


### FIXED CODE ###

N,K=list(map(int,input().strip().split(" ")))
H=list(map(int,input().strip().split(" ")))
dp=[0]+[10**10]*(N-1)
for i in range(1,N):
    temp=0
    for j in range(i-K,i):
        if j>=0:
            dp[i]=min(dp[i],dp[j]+abs(H[i]-H[j]))
print(dp[-1])
### BUGGY CODE ###

import sys
import numpy as np


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    solo_invs = [0] + [f * i % MOD for f, i in zip(factorials, invs[1:])]

    return factorials, invs, solo_invs


def decompose_inverses(solo_invs, MOD):
    # 各整数 g に対して、g の約数である各 i について dcm[i] を全て足すと 1/g になるような数列を作成
    dcm = np.array(solo_invs, dtype=np.int64)
    for i in range(1, len(dcm)):
        dcm[2 * i::i] -= dcm[i]
    dcm %= MOD
    return dcm


n, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
cnt = np.bincount(aaa)
LIMIT = len(cnt) - 1
facts, invs, solo_invs = prepare(LIMIT, MOD)
dcm = decompose_inverses(solo_invs, MOD)
idx = np.arange(LIMIT + 1, dtype=np.int64)
base1 = idx * cnt
base2 = idx ** 2 * cnt

ans = 0
inv2 = solo_invs[2]
for d in range(1, LIMIT + 1):
    ans = (ans + int(dcm[d]) * int(base1[d::d].sum() ** 2 - base2[d::d].sum()) * inv2) % MOD
print(ans)


### FIXED CODE ###

import sys


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    solo_invs = [0] + [f * i % MOD for f, i in zip(factorials, invs[1:])]

    return factorials, invs, solo_invs


def decompose_inverses(solo_invs, MOD):
    # 各整数 g に対して、g の約数である各 i について dcm[i] を全て足すと 1/g になるような数列を作成
    n = len(solo_invs)
    dcm = solo_invs[:]
    for i in range(1, n):
        d = dcm[i]
        for j in range(2 * i, n, i):
            dcm[j] -= d
    for i in range(1, n):
        dcm[i] %= MOD
    return dcm


n, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
LIMIT = max(aaa)
count = [0] * (LIMIT + 1)
double = [0] * (LIMIT + 1)
for a in aaa:
    count[a] += a
    double[a] += a * a
_, _, solo_invs = prepare(LIMIT, MOD)
dcm = decompose_inverses(solo_invs, MOD)

ans = 0
inv2 = solo_invs[2]
for d in range(1, LIMIT + 1):
    ans = (ans + dcm[d] * (sum(count[d::d]) ** 2 - sum(double[d::d])) * inv2) % MOD
print(ans)
### BUGGY CODE ###

import sys

S = input()
count,chk_count=0,0
for i in range(sys.maxsize):
    chk_count=count
    count+=S.count("BW")
    S=S.replace("BW","WB")
    if chk_count == count:
        print(count)
        exit()

### FIXED CODE ###


S = input()
count=0
w=0
for i in range(len(S)):
    if S[i] =="W":
        count+=i-w
        w+=1
print(count)
### BUGGY CODE ###

s = input()
q = int(input())
que = [list(map(str, list(input().split()))) for i in range(q)]

hanten = 0
for i in range(q):
    if que[i][0] == "1":
        if hanten == 0:
            hanten = 1
        else:
            hanten = 0
    elif que[i][0] == "2":
        if hanten == 0:
            if que[i][1] == "1":
                sub = [que[i][2], s]
                s = ''.join(sub)
            elif que[i][1] == "2":
                sub = [s,que[i][2]]
                s = ''.join(sub)
        else:
            if que[i][1] == "1":
                sub = [s,que[i][2]]
                s = ''.join(sub)
            elif que[i][1] == "2":
                sub = [que[i][2], s]
                s = ''.join(sub)
if hanten == 1:
    s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
que = [list(map(str, list(input().split()))) for i in range(q)]

hanten = 0
left = ""
right = ""
for i in range(q):
    if que[i][0] == "1":
        if hanten == 0:
            hanten = 1
        else:
            hanten = 0
    elif que[i][0] == "2":
        if hanten == 0:
            if que[i][1] == "2":
                sub = [right, que[i][2]]
                right = ''.join(sub)
            elif que[i][1] == "1":
                sub = [que[i][2], left]
                left = ''.join(sub)
        else:
            if que[i][1] == "2":
                sub = [que[i][2],left]
                left = ''.join(sub)
            elif que[i][1] == "1":
                sub = [right,que[i][2]]
                right = ''.join(sub)

sub = [left, s, right]
s = ''.join(sub)
if hanten == 1:
    s = s[::-1]
print(s)
### BUGGY CODE ###

from fractions import gcd
K = int(input())
answer = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            answer += gcd(gcd(i,j),k)

print(answer)

### FIXED CODE ###

from math import gcd
K = int(input())
answer = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            answer += gcd(gcd(i,j),k)

print(answer)
### BUGGY CODE ###

s = input()
k = int(input())

_all = []

for i in range(1, len(s)+1):
	for j in range(len(s)-i+1):
		_all.append(s[j:j+i])


_set = set(_all)
print(sorted(_set)[k-1])

### FIXED CODE ###

s = input()
k = int(input())

_all = []

for i in range(1, min(k+1, len(s)+1)):
	for j in range(len(s)-i+1):
		sub = s[j:j+i]
		if sub not in _all:
			_all.append(sub)

print(sorted(_all)[k-1])
### BUGGY CODE ###

import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
di = []
for j in range(n):
    i = ls[i-1]
    if i in di:
        print(-1)
        sys.exit()
    di.append(i)
    k += 1
    if i == 2:
        break
print(k)

### FIXED CODE ###

import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
for j in range(n):
    i = ls[i-1]
    k += 1
    if i == 2:
        print(k)
        sys.exit()
print(-1)
### BUGGY CODE ###

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

dp = [[0] * k for _ in range(n + 1)]
dp[0][0] = 1
for i, e in enumerate(a, 1):
    for j in range(k):
        dp[i][j] = dp[i-1][j]

    for j in range(k - e):
        if dp[i-1][j]:
            dp[i][j+e] = 1

dp2 = [[0] * k for _ in range(n + 1)]
dp2[0][0] = 1
for i, e in enumerate(a[::-1], 1):
    for j in range(k):
        dp2[i][j] = dp2[i-1][j]

    for j in range(k - e):
        if dp2[i-1][j]:
            dp2[i][j+e] = 1

ans = 0
for i, e in enumerate(a, 1):
    li = [j for j in range(k) if dp[i-1][j]]
    li2 = [j for j in range(k) if dp2[n-i][j]]

    j = len(li2) - 1
    mx = 0
    for e2 in li:
        while j > 0 and e2 + li2[j] >= k:
            j -= 1

        if e2 + li2[j] < k:
            mx = max(mx, e2 + li2[j])

    if mx + e < k:
        ans += 1

print(ans)


### FIXED CODE ###

import numpy as np


def check(x):
    dp = np.zeros(k, np.bool)
    dp[0] = True
    for e in a[:x] + a[x+1:]:
        dp[e:] |= dp[:-e]

    return dp[-a[x]:].any()


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

a.sort()

lb = -1
ub = n
while ub - lb > 1:
    m = (lb + ub) // 2
    if check(m):
        ub = m
    else:
        lb = m

print(ub)
### BUGGY CODE ###


k, s = list(map(int, input().split()))

count=0

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


### FIXED CODE ###


k, s = list(map(int, input().split()))

count=0

for x in range(0, k+1):
    for y in range(0, k+1):
      if 0<=s-(x+y)<=k :
          count+=1 

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

from itertools import permutations

N, M, R = [int(n) for n in input().split()]
r = [int(n)-1 for n in input().split()]
d = [[100000000]*N for n in range(N)]

for i in range(N):
  d[i][i] = 0

for m in range(M):
  A, B, C = [int(n) for n in input().split()]
  A-=1
  B-=1
  d[A][B] = C
  d[B][A] = C

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][k]+d[k][j], d[i][j])

res = 1000000000
for perm in permutations(range(R)):
  s = 0
  for i in range(R-1):
    s += d[r[perm[i]]][r[perm[i+1]]]
  res = min(s, res)

print(res)

### FIXED CODE ###

from itertools import permutations

N, M, R = [int(n) for n in input().split()]
r = [int(n)-1 for n in input().split()]
d = [[100000000]*N for n in range(N)]

for i in range(N):
  d[i][i] = 0

for m in range(M):
  A, B, C = [int(n) for n in input().split()]
  A-=1
  B-=1
  d[A][B] = C
  d[B][A] = C

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][k]+d[k][j], d[i][j])

res = 1000000000
for perm in permutations(range(R)):
  s = 0
  for i in range(R-1):
    s += d[r[perm[i]]][r[perm[i+1]]]
  res = min(s, res)

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

import re


n, q = map(int, input().split())
s = input()
lis = [x.span() for x in re.finditer("AC", s)]
for i in range(q):
    l, r = map(int, input().split())
    cnt = 0
    for j in lis:
        if l-1 <= j[0] and j[1] <= r:
            cnt += 1
    print(cnt)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lis = [0]
cnt = 0
for i in range(1, n):
    if s[i-1:i+1] == "AC":
        cnt += 1
        lis.append(cnt)
    else:
        lis.append(cnt)
for i in range(q):
    l, r = map(int, input().split())
    print(lis[r-1] - lis[l-1])
### BUGGY CODE ###

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

def func1(a):
    a.sort()
    cnt=0
    chker=[]
    for i in a:
        candiv=False
        if a.count(i)>1:
            candiv=True
            if chker.count(i)==0:
                chker.append(i)
        else:
            for j in chker:
                if j*2>i:
                    break
                if i%j==0:
                    candiv=True
                    break
        if candiv==False:
            cnt+=1
            chker.append(i)
    print(cnt)
func1(a)


### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        j=1
        while 1:
            j+=1
            if i*j>max:
                break
            dp[i*j]=True
for i in range(len(a)-1):
    if a[i]==a[i+1]:
        dp[a[i]]=True
cnt=0
for i in a:
    if dp[i]==False:
        cnt+=1

print(cnt)