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

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
route_list = [[] for i in range(n)]
for i in range(n):
    now = (i + 1)
    now_score = 0
    while p[now - 1] != (i + 1):
        route_list[i].append(now_score)
        now = p[now - 1]
        now_score += c[now - 1]
    route_list[i].append(now_score)
# 多分0でいい
ans = -(10**9 * 5000)
for i in range(n):
    # iからスタートする場合
    score = 0
    remain_move = 0
    cand_score = 0
    if route_list[i][-1] + c[i] > 0 and k > len(route_list[i]):
        # 一周以上する可能性がある場合
        # n週して、残りの動ける回数
        # print("Yes")
        round_count = (k // len(route_list[i])) - 1
        remain_move = k - round_count * len(route_list[i])
        cand_score = round_count * ( route_list[i][-1] + c[i] )
    else:
        remain_move = k
        score = -(10**9 * 5000)
        cand_score = 0
    now = i
    for j in range(remain_move):
        now = p[now] - 1
        cand_score += c[now]
        score = max(score, cand_score)
    # print("start : {}  score : {}".format(i,score))
    ans = max(score, ans)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
point_start_with = [0 for i in range(n)]
roop_count = [1 for i in range(n)]
for i in range(n):
    now = (i + 1)
    now_score = 0
    while p[now - 1] != (i + 1):
        now = p[now - 1]
        now_score += c[now - 1]
        roop_count[i] += 1
    point_start_with[i] = now_score
# 多分0でいい
ans = -(10**9 * 5000)
for i in range(n):
    # iからスタートする場合
    score = 0
    remain_move = 0
    cand_score = 0
    if point_start_with[i] + c[i] > 0 and k > roop_count[i]:
        # 一周以上する可能性がある場合
        # n週して、残りの動ける回数
        # print("Yes")
        round_count = (k // roop_count[i]) - 1
        remain_move = k - round_count * roop_count[i]
        cand_score = round_count * ( point_start_with[i] + c[i] )
    else:
        remain_move = min(k,roop_count[i])
        score = -(10**9 * 5000)
        cand_score = 0
    now = i
    for j in range(remain_move):
        now = p[now] - 1
        cand_score += c[now]
        score = max(score, cand_score)
    # print("start : {}  score : {}".format(i,score))
    ans = max(score, ans)
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
nl = sorted(l,reverse=True)
c = 0
for i in range(n-2):
    a = nl[i]
    for j in range(n-1,i,-1):
        for k in range(i+1,j):
            if a<(nl[j]+nl[k]):
                c+=1
            else:
                break
print(c)

### FIXED CODE ###

import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
g=0
for ai in range(n-2):
    for bi in range(ai+1,n-1):
        g+=max(0,bisect.bisect_left(l,l[bi]+l[ai])-1-bi)
print(g)
### BUGGY CODE ###

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

A.sort(reverse=True)
#print(A)

B=A[0:min(N,M)]

for i in range(M):
    idx = B.index(max(B))

    B[idx] = int(B[idx] / 2.0)
#    A.sort(reverse=True)

ans = 0
for i in range(N):
    if i < len(B):
        ans+=B[i]
    else:
        ans += A[i]

print(ans)

### FIXED CODE ###

import heapq

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

for i in range(N):
    A[i] = -A[i]

heapq.heapify(A)

for j in range(M):
    a = heapq.heappop(A)
    b = -1*((-a) // 2)
    heapq.heappush(A,b)

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

import itertools,copy
cost = 0
N,M,X = map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(N)]
combi = itertools.permutations(range(N),N)
sumx = [0]*M
sumfx = [0]*M
for j in range(N):
    for i in range(M):
        sumx[i]+=ca[j][i+1]
        if sumx[i]>=X:
            sumfx[i]=1
    cost += ca[j][0]
ans = cost
if sum(sumfx) != M:
    print(-1)
    
else:
    for a in combi:
        x = copy.copy(sumx)
        fx = copy.copy(sumfx)
        c = cost
        for i in range(len(a)):
            for j in range(1,M+1):
                x[j-1] -= ca[a[i]][j]
                if x[j-1]<X:
                    fx[j-1] = 0

            if sum(fx)!=M:
                break
            else:
                c -= ca[a[i]][0]
                ans = min(c,ans)

    print(ans)

### FIXED CODE ###

import itertools
import numpy as np
 
N,M,X = map(int,input().split())
ca = ([list(map(int,input().split())) for _ in range(N)])
ca = np.array(ca)
sumX = sum(ca)[1:]
sumcos = sum(ca)[0]
cost = sumcos
if sum(sumX>=X)<M:
    print(-1)
else:
    for j in range(1,N+1):
        for a in itertools.combinations(range(1,N+1),j):       
            x = sum(ca)[1:]
            fx = np.array([0]*M)
            c = sumcos
            for i in range(len(a)):
                x -= ca[a[i]-1][1:]
                c -= ca[a[i]-1][0]
                if sum(x>=X)<M:
                    break
                else:
                    cost = min(c,cost)
    print(cost)
### BUGGY CODE ###

# C問題
n, x = map(int, input().split())
a = list(map(int, input().split()))
new_a = []
new_a += a
if a[0] > x:
    new_a[0] = x
for i in range(n-1):
    while True:
        if new_a[i] + new_a[i+1] > x:
            new_a[i+1] -= 1
        if new_a[i] + new_a[i+1] <= x:
            break

print(sum(a) - sum(new_a))

### FIXED CODE ###

# C問題
n, x = map(int, input().split())
a = list(map(int, input().split()))
new_a = []
new_a += a
if a[0] > x:
    new_a[0] = x
for i in range(n-1):
    while True:
        if new_a[i] + new_a[i+1] > x:
            new_a[i+1] = x-new_a[i]
        if new_a[i] + new_a[i+1] <= x:
            break

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

from collections import deque
 
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
stage = ['#'+input()+'#' for i in range(h)]
stage = ['#'*(w+2)] + stage + ['#'*(w+2)]
queue = deque([(ch,cw)])
check = [[1]*(w+2) for i in range(h+2)]
searched_temp = [(ch,cw)]
count = 0
 
while True:
  searched = searched_temp
  
  while len(queue):
    v = queue.popleft()
    if v == (dh,dw):
      print(count)
      exit()
 
    if stage[v[0]-1][v[1]] == '.' and check[v[0]-1][v[1]]:
      queue.append((v[0]-1,v[1]))
      check[v[0]-1][v[1]] = 0
      searched.append((v[0]-1,v[1]))
    if stage[v[0]+1][v[1]] == '.' and check[v[0]+1][v[1]]:
      queue.append((v[0]+1,v[1]))
      check[v[0]+1][v[1]] = 0
      searched.append((v[0]+1,v[1]))
    if stage[v[0]][v[1]-1] == '.' and check[v[0]][v[1]-1]:
      queue.append((v[0],v[1]-1))
      check[v[0]][v[1]-1] = 0
      searched.append((v[0],v[1]-1))
    if stage[v[0]][v[1]+1] == '.' and check[v[0]][v[1]+1]:
      queue.append((v[0],v[1]+1))
      check[v[0]][v[1]+1] = 0
      searched.append((v[0],v[1]+1))
  
  count += 1
  searched_temp = []
  for s in searched:
    for i in range(-2,3):
      for j in range(-2,3):
        y = s[0] + i
        x = s[1] + j
        if 1 <= y and y <= h and 1 <= x and x <= w:
          if stage[y][x] == '.' and check[y][x]:
            check[y][x] = 0
            queue.append((y,x))
            searched_temp.append((y,x))
          
  if len(queue) == 0:
    print(-1)
    break

### FIXED CODE ###

from collections import deque
 
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
stage = ['#'+input()+'#' for i in range(h)]
stage = ['#'*(w+2)] + stage + ['#'*(w+2)]
queue = deque([(ch,cw)])
check = [[1]*(w+2) for i in range(h+2)]
searched_temp = [(ch,cw)]
count = 0
 
while True:
  searched = searched_temp
  
  while len(queue):
    v = queue.popleft()
    if v == (dh,dw):
      print(count)
      exit()
 
    if stage[v[0]-1][v[1]] == '.' and check[v[0]-1][v[1]]:
      queue.append((v[0]-1,v[1]))
      check[v[0]-1][v[1]] = 0
      searched.append((v[0]-1,v[1]))
    if stage[v[0]+1][v[1]] == '.' and check[v[0]+1][v[1]]:
      queue.append((v[0]+1,v[1]))
      check[v[0]+1][v[1]] = 0
      searched.append((v[0]+1,v[1]))
    if stage[v[0]][v[1]-1] == '.' and check[v[0]][v[1]-1]:
      queue.append((v[0],v[1]-1))
      check[v[0]][v[1]-1] = 0
      searched.append((v[0],v[1]-1))
    if stage[v[0]][v[1]+1] == '.' and check[v[0]][v[1]+1]:
      queue.append((v[0],v[1]+1))
      check[v[0]][v[1]+1] = 0
      searched.append((v[0],v[1]+1))
  
  count += 1
  searched_temp = []
  for s in searched:
    for i in range(-2,3):
      for j in range(-2,3):
        y = s[0] + i
        x = s[1] + j
        if 1 <= y and y <= h and 1 <= x and x <= w:
          if stage[y][x] == '.' and check[y][x]:
            check[y][x] = 0
            queue.append((y,x))
            searched_temp.append((y,x))
          
  if len(queue) == 0:
    print(-1)
    break
### BUGGY CODE ###

from itertools import permutations, combinations
n = int(input())
s = []
for _ in range(n):
  s.append(input())

ilist = []
for a in range(len(s)):
  ilist.append(list(s[a]))
  a += 1
#print(ilist)
li = list(combinations(ilist, 2))
trial = len(li)#何回比較するか求める
ans = 0 #answer
for b in range(len(li)):
  li[b][0].sort()
  li[b][1].sort()
  if(li[b][0] == li[b][1]):
    ans += 1
print(ans)

### FIXED CODE ###

from collections import *
 
n = int(input())
dic = defaultdict(int)
for i in range(n):
  dic["".join(sorted(input()))] += 1
 
ans = 0
for k,v in dic.items(): 
  ans += int(v*(v-1)/2)
  #ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
t=1
for i in range(k):
	t*=l[i]
j=0
for i in range(k,n):
	f=t//l[j]
	f*=l[i]
	if f>t:
		print("Yes")
	else:
		print("No")
	t=f
	j+=1

### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
j=0
for i in range(k,n):

	if l[i]>l[j]:
		print("Yes")
	else:
		print("No")
	j+=1
### BUGGY CODE ###

s = input()
mmax = 0
def function(string):
  global mmax
  n = len(string)
  if n<2:
    return
  if n%2==0:
    if string[0:int(n/2)]==string[int(n/2):n]:
      mmax = max(mmax, n)
  function(string[0:n-1])
  function(string[1:n])
function(s[0:len(s)-1])
function(s[1:len(s)])
print(mmax)

### FIXED CODE ###

s = input()
mmax = 0
n = len(s)
while(n>1):
  s = s[0:n-1]
  n = len(s)
  if n<2:
    break
  if s[0:int(n/2)]==s[int(n/2):n]:
    mmax = max(mmax, n)
print(mmax)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 19 21:27:49 2020

@author: arute
"""


from sys import stdin

import time
import numpy as np

############################################

# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])

data = []
write = stdin.readline().split()
for i in range(N-1):
    data.append(int(write[i]))

data = np.asarray(data)

out = ""
for i in range(N):
    out+=str((np.sum(data==(i+1))))+"\n"

print(out)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 19 21:27:49 2020

@author: arute
"""


from sys import stdin

import time
import numpy as np


############################################

# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])

data = []
write = stdin.readline().split()
for i in range(N-1):
    data.append(int(write[i]))

data = np.asarray(data)

out = np.zeros(N)
for d in data:
    out[d-1] += 1

o = ""
for l in out:
    o+=str(int(l))+"\n"

print(o)
### BUGGY CODE ###

import math

num = int(input())

sum_gcd = 0

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

print(sum_gcd)

### FIXED CODE ###

import math

K = int(input())
print(sum([math.gcd(math.gcd(i, j), k) for i in range(1, K+1) for j in range(1, K+1) for k in range(1, K+1)]))
### BUGGY CODE ###

N = int(input())

def sum(n):
    s = 0
    if n == 0:
        return 0
    else:
        while n != 0:
            s += n % 10
            n = n // 10
        return int(s)

        
import math
m = sum(N)
if N != 0:
    for i in range(int(math.log10(N)) + 1):
        n = sum((N // 10**i) * 10**i - 1)
        if n > m:
            m = n
else:
    m = 0


print(m)

### FIXED CODE ###

a = input()
a = list(a)
l = len(a)
for i in range(l):
    a[i] = int(a[i])
m = sum(a)
for i in range(l):
    n = a[i]-1 + 9*(l-i-1)
    if n > m:
        m = n
print(m)
### BUGGY CODE ###

s = input()

ans = 0

while "ABC" in s:
    cnt = s.count("ABC")
    s = s.replace("ABC","BCA",cnt)
    ans += cnt
    
print(ans)

### FIXED CODE ###

s = input()
 
ans = 0
s = s.replace("BC","D")
cnt_A = 0
 

for i in s:
    if i == "A":
        cnt_A += 1
    elif i == "D":
        ans += cnt_A
    else:
        cnt_A = 0

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

# D - Sum of Divisors
N = int(input())
ans = (1 + N) * N

for i in range(2, N//2 + 1):
	j = 2
	
	while True:
		if i * j <= N:
			
			ans += i * j
			j += 1
		else:
			break

print(ans - 1)

### FIXED CODE ###

# D - Sum of Divisors
N = int(input())
ans = (1 + N) * N

for i in range(2, N//2 + 1):
	j = 2
	
	while True:
		if i * j <= N:
			
			ans += i * j
			j += 1
		else:
			break

print(ans - 1)
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                ans += 1

print(ans)

### FIXED CODE ###

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

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

n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
pre = 0
for s in S[::-1]:
  pre = MS(t,int(s),pre)
  M[pre] += 1
  t *= 10

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)


### FIXED CODE ###

n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
    i = int(i)
    now += i*t
    now %= p
    M[now] += 1
    t = t*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)
### BUGGY CODE ###

import numpy as np
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))

b=[]
for i in range(n):
  b.append((1+a[i])/2)
  
ans=0
for i in range(n-k+1):
  tmp=np.sum(b[i:i+k])
  if ans<tmp:
    ans=tmp
    
print(ans)

### FIXED CODE ###

n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
  
ans=0
for i in range(k):
  ans += (a[i]+1)/2
past=ans
for i in range(1,n-k+1):
  tmp = past - (a[i-1]+1)/2 +  (a[i+k-1]+1)/2
  if ans<tmp:
    ans=tmp
  past = tmp
    
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 10 ** 6

for i in range(n):
    a = s[:i].count("W")
    b = s[i:].count("E")
    ans = min(ans,a+b)
print(ans)



### FIXED CODE ###

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

tmp = s[1:].count("E")
ans = tmp
for i in range(n-1):
    if s[i] == "W":
        tmp += 1
    if s[i+1] == "E":
        tmp -= 1
    ans = min(ans,tmp)
print(ans)
### BUGGY CODE ###

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

a_ol = {}
def_count = 0
for i in a_uni:
    a_co = a.count(i)
    a_ol[i] = a_co
    def_count += a_co * (a_co - 1) // 2

for k in range(n):
    print(def_count - a_ol[a[k]] + 1)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))


a_ol = Counter(a)
def_count = 0
for item in a_ol.items():
    a_co = item[1]
    def_count += a_co * (a_co - 1)

def_count //= 2

for k in a:
    print(def_count - a_ol[k] + 1)
### BUGGY CODE ###

import heapq

N,M = (int(i) for i in input().split())
A = list(map(int,input().split()))
A.sort()
D = []
len = 0
for i in range(M):
    B,C = (int(i) for i in input().split())
    D.extend([C]*B)
    len += B
D.sort()
cnt = min(N,len)
for i in range(cnt):
    if A[0] < D[-1]:
        heapq.heapreplace(A,D[-1])
        D.pop(-1)
    else:
        break
print(sum(A))


### FIXED CODE ###

import heapq

N,M = (int(i) for i in input().split())
A = list(map(int,input().split()))
A.sort()
D = []
len = 0
BC = [0] * M

for i in range(M):
    BC[i] = list(map(int,input().split()))
BC.sort(key = lambda x:x[1],reverse = True)
for i in range(M):
    D.extend([BC[i][1]] * BC[i][0])
    len += BC[i][0]
    if len > N:
        break
cnt = min(N,len)
for i in range(cnt):
    if A[0] < D[i]:
        heapq.heapreplace(A,D[i])
    else:
        break
print(sum(A))
### BUGGY CODE ###

def unzip(li):
  return map(list, zip(*li))

N, M = map(int, input().split())
tmp_A = []
tmp_B = []

for i in range(N):
  a,b = map(int, input().split())
  tmp_A.append(a)
  tmp_B.append(b)
  
C = sorted(zip(tmp_A,tmp_B))
A, B = unzip(C)
ans = 0
count = 0
while(count < M):
  min_A = A[0]
  B_min = B[0]
  if count + B_min >= M:
    print(ans + min_A * (M - count))
    break
  else:
    ans += min_A * B_min
    count += B_min
    del A[0]
    del B[0]


### FIXED CODE ###

def unzip(li):
  return map(list, zip(*li))

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

for i in range(N):
  a,b = map(int, input().split())
  tmp_C[i] = (a,b)
  
C = sorted(tmp_C)
A, B = unzip(C)
ans = 0
count = 0
cur = 0
while(count < M):
  min_A = A[cur]
  B_min = B[cur]
  if count + B_min >= M:
    print(ans + min_A * (M - count))
    break
  else:
    ans += min_A * B_min
    count += B_min
    cur += 1
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
h.sort()
ans=0
h.reverse()
for i in range(k):
  if len(h)>=1:
    h.pop(0)
for i in h:
  if len(h)>=1:
    ans+=i
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
h.sort()
ans=0
h.reverse()
if k<n:
  for i in range(k,n):
    ans+=h[i]
print(ans)
### BUGGY CODE ###

n, k = map(int,input().split())
xs = []
ys = []
points = []
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    points.append((x, y))

                
min_ = float('inf')
for leftx in xs:
    for rightx in xs:
        if leftx >= rightx:
            continue
        for downy in ys:
            for upy in ys:
                if downy >= upy:
                    continue
                cnt = 0
                for tx, ty in points:
                    if (leftx <= tx <= rightx) and (downy <= ty <= upy):
                        cnt += 1
                
                if cnt >= k:
                    yoko = rightx - leftx
                    tate = upy - downy
                    men = yoko*tate
                    if men < min_:
                        min_ = men
print(min_)
                        

### FIXED CODE ###

n, k = map(int,input().split())
ps = [tuple(map(int,input().split())) for i in range(n)]

sx = sorted(ps,key = lambda x: x[0]) # x座標でソート
nx = list(enumerate(sx)) # 頂点番号を付加
ans = 5e18

for f, (x1,y1) in nx[:n-k+1]: # 左辺の頂点
    for e, (x2,y2) in nx[f+k-1:]: # 右辺の頂点
        dx = x2 - x1 # 横
        sy = sorted(y for x,y in sx[f:e+1]) # 含まれる頂点をy座標でソート
        for y3,y4 in zip(sy,sy[k-1:]): # y3=下辺の頂点，y4=上辺の頂点
            if y3 <= y1 and y4 >= y2: # 左右辺の頂点を含むこと
                ans = min(ans, dx * (y4 - y3))

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

import collections

n = int(input())
a = list(map(int, input().split()))
#n = 2 * 10**5
#a = [i for i in range(1, n+1)]

a.sort()
def Eratosthenes(x):
    c = collections.Counter(x)
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in range(1, nmax+1):
        if not is_prime[i]:
            continue
        if i in x:
            for j in range(i*2, nmax+1, i):
                is_prime[j] = False
    for i in range(1, nmax+1):
        if c[i] > 1:
            is_prime[i] = False
    for i in range(1, nmax+1):
        if is_prime[i] == True and i in a:
            cnt += 1
    print(cnt)

Eratosthenes(a)

### FIXED CODE ###

from collections import Counter

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

a.sort()
cnt = 0
nmax = a[-1]
table = [True] * (nmax+1)
c = Counter(a)

duplicate = []
for i in c.keys():
    if c[i] > 1:
        duplicate.append(i)
for i in a:
    if not table[i]:
        continue
    if not i in duplicate:
        cnt += 1
    for j in range(i*2, nmax+1, i):
        table[j] = False
print(cnt)
### BUGGY CODE ###

# Not Divisible

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

A.sort()
ok = []

while 0 < len(A):
    div = True
    for i in range(1, len(A)):
        if A[0] == A[i]:
            div = False
            A[i] = 0
        elif A[i] % A[0] == 0:
            A[i] = 0
    if div:
        ok.append(A[0])
    A[0] = 0
    A = list(filter(lambda a: 0 < a, A))

print(len(ok))


### FIXED CODE ###

# Not Divisible

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

check = [0] * 1000001
A.sort()

ok = [-1]
p = 0
for a in A:
    if a == p:
        if ok[-1] == p:
            ok = ok[:-1]
        continue
    p = a
    if check[a] == 1:
        continue
    for i in range(a, 1000001, a):
        check[i] = 1
    ok.append(a)

print(len(ok) - 1)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from fractions import gcd

l = a[0]
for i in range(1,n):
  l = l*a[i]//gcd(l,a[i])

b = [0]*n
ans = 0
for i in range(n):
  b[i] = l//a[i]
  ans += b[i]%mod

print(ans%mod)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from fractions import gcd

l = a[0]
for i in range(1,n):
  l = l*a[i]//gcd(l,a[i])

ans = 0
for i in range(n):
  ans += l//a[i]

print(ans%mod)
### BUGGY CODE ###

import itertools
from bisect import bisect_left

def index(a, x):
    'Find leftmost index of item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return i
    return False

def main():
    N = int(input())
    S = input()
    lst = list(S)

    a = []
    for i,j,k in itertools.combinations(range(N), 3):
        if i < j < k:
            s = int(str(lst[i])+str(lst[j])+str(lst[k]))

            idx = bisect_left(a, s)

            if idx == len(a):
                a.append(s)
            
            elif a[idx] != s:
                a.insert(idx, s)
            
            if len(a) == 1000:
                break
    print(len(a))

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    lst = list(S)

    a = ['{:03d}'.format(i) for i in range(1000)]
    count = 0
    for i in range(len(a)):
        m,n,o = 0,1,2
        s = list(a[i])
        while m < n < o < len(lst) :
            if s[0] != lst[m]:
                m += 1
                n += 1
                o += 1
            elif s[1] != lst[n]:
                n += 1
                o += 1
            elif s[2] != lst[o]:
                o += 1
            else:
                count += 1
                break

    print(count)

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

n = int(input())
s = list(map(str, input()))

def solve(k):
  k1, k2, k3 = list(k)
  ans = 0
  for i1 in range(n):
    if s[i1] == k1:
      for i2 in range(i1+1, n):
        if s[i2] == k2:
          for i3 in range(i2+1, n):
            if s[i3] == k3:
              return 1
  return 0

ans = 0
for k in range(1000):
  k = '{:0=3}'.format(k)
  ans += solve(k)

print(ans)

### FIXED CODE ###

n = int(input())
s = list(map(str, input()))

def solve(k):
  k1, k2, k3 = list(k)
  ans = 0
  flag = 0
  for i1 in range(n):
    if s[i1] == k1:
      for i2 in range(i1+1, n):
        if s[i2] == k2:
          for i3 in range(i2+1, n):
            if s[i3] == k3:
              flag = 1
              break
          break
      break
  if flag:
    return 1
  else:
    return 0

ans = 0
for k in range(1000):
  k = '{:0=3}'.format(k)
  ans += solve(k)

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

n=int(input())
a=[]
for i in range(n):
  a.append(int(input()))
i=0
count=1
while(1):
  if a[i]==1:
    frag=-1
    break
  elif a[i]==2:
    frag=count
    break
  else:
    i=a[i]-1
    count+=1
print(frag)  

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
  a.append(int(input()))
i=0
count=1
frag=-1
for j in range(n):
  if a[i]==2:
    frag=count
    break
  else:
    i=a[i]-1
    count+=1
print(frag)