Harryxun/stf_run huggingface dataset:
tree = dict()
cost = dict()

N = int(input())
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [False for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == False:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

tree = dict()
cost = dict()

N = int(input())
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [1000000000000000 for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == 1000000000000000:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])
N, M = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(M)]

ans = [-1] * N

for i in range(M):
    s = sc[i][0] - 1
    c = sc[i][1]
    if ans[s] is -1:
        ans[s] = c
    elif not ans[s] == c:
        print(-1)
        exit(-1)
if ans[-1] == 0:
    print(-1)
    exit(-1)

a = 0
for i in range(N):
    if ans[i] is -1:
        ans[i] = 0
    a += ans[i]*10**(N-i-1)

print(a)


### FIXED CODE ###

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

ans = [-1] * N

for i in range(M):
    s = sc[i][0] - 1
    c = sc[i][1]
    if ans[s] is -1:
        ans[s] = c
    elif not ans[s] == c:
        print(-1)
        exit()

if N!=1 and ans[0] == 0:
    print(-1)
    exit()

a = 0
for i in range(N):
    if ans[i] is -1:
        if i == 0 and N!= 1:
            ans[i] = 1
        else:
            ans[i] = 0
    a += ans[i]*10**(N-i-1)

print(a)
コンテスト時間: 2018-07-21(土) 21:00 ~ 2018-07-21(土) 22:40 (100分)AtCoderホームへ戻る
 トップ
 問題
 質問
 提出
 提出結果
 順位表
 バーチャル順位表
 コードテスト
 解説
コードテスト
言語

ソースコード
)
1
N = int(input())
2
a = list(map(int, input().split()))
3
a.sort(reverse=True)
4
​
5
# ユークリッドの互除法により最大公約数を求める
6
ans = 0
7
val1, val2 = a[0], a[1]
8
while 1:
9
  if val1 % val2 == 0:
10
    ans = a[0]*a[1]/val2
11
    break
12
  else:
13
    tmp = val2
14
    val2 = val1 % val2
15
    val1 = tmp
16
​
17
for i in range(2, N):
18
  val1, val2 = ans, a[i]
19
  while 1:
20
    if val1 % val2 == 0:
21
      ans = ans*a[i]/val2
22
      break
23
    else:
24
      tmp = val2
25
      val2 = val1 % val2
26
      val1 = tmp
27
​
28
f_ans = 0
29
for i in range(N):
30
  f_ans += (ans-1)%a[i]
31
print(int(f_ans))
32
  
33
      
34
  
※ 512 KiB まで
※ ソースコードは「Main.拡張子」で保存されます

  
標準入力
7
994 518 941 851 647 2 581
※ 512 KiB まで

終了コード	0
実行時間	17 ms
メモリ	2964 KB
標準出力
4527

標準エラー出力
FacebookTwitterHatena共有
ルール 用語集
利用規約 プライバシーポリシー 個人情報保護方針 企業情報 よくある質問 お問い合わせ 資料請求
Copyright Since 2012 ©AtCoder Inc. All rights reserved.

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

# ユークリッドの互除法により最大公約数を求める
ans = 0
val1, val2 = a[0], a[1]
while 1:
  if val1 % val2 == 0:
    ans = a[0]*a[1]//val2
    break
  else:
    tmp = val2
    val2 = val1 % val2
    val1 = tmp

for i in range(2, N):
  val1, val2 = ans, a[i]
  while 1:
    if val1 % val2 == 0:
      ans *= a[i]//val2
      break
    else:
      tmp = val2
      val2 = val1 % val2
      val1 = tmp

f_ans = 0
for i in range(N):
  f_ans += (ans-1)%a[i]
print(int(f_ans))
M, N = map(int, input().split())

if M > N:
  body = N
  numm = M
else:
  body = M
  numm = N

ret = ''
for i in numm:
  ret += str(body)
print(ret)

### FIXED CODE ###

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

if M > N:
  body = N
  numm = M
else:
  body = M
  numm = N

ret = ''
for i in range(numm):
  ret += str(body)
print(ret)
n,m=map(int,input().split())
lst=[[]*m for i in range(n)]
for i in range(n):
    lst[i]=list(map(int,input().split()))
lst2=[[]*1 for i in range(m)]
for i in range(m):
    lst2[i]=list(map(int,input().split()))
for i in range(n):
    x=0
    for j in range(m):
        x=x+lst[i][j]*lst2[j]
    print("%d"%(x))



### FIXED CODE ###

n,m=map(int,input().split())
lst=[[]for i in range(n)]
for i in range(n):
    lst[i]=list(map(int,input().split()))
lst2=[[]*1 for i in range(m)]
for i in range(m):
    lst2[i]=int(input())
for i in range(n):
    x=0
    for j in range(m):
        x=x+lst[i][j]*lst2[j]
    print("%d"%(x))
import heapq

n,m = map(int, raw_input().split(' '))
elems = map(int, raw_input().split(' '))
elems.sort()

heap = [(-elems[i] - elems[-1], i,len(elems) - 1) for i in range(len(elems))]
heapq.heapify(heap)
cumul = 0

while(m):
	m -=1
	v, i, j = heapq.heappop(heap)
	cumul -= v
	if j -1 >=0: heapq.heappush(heap, (-elems[i] - elems[j-1], i, j - 1))
print cumul

### FIXED CODE ###

b,a = raw_input().split(' ')
print a + b
S=list(int(input()))
if S[0]==S[1] or S[1]==S[2] or S[2]==S[3] or S[3]==S[4]:
  print("Bad")
else:
  print("Good")

### FIXED CODE ###

S=list(input())
if S[0]==S[1] or S[1]==S[2] or S[2]==S[3] :
  print("Bad")
else:
  print("Good")
def main():
    """
    2^20 = 1,048,576
    q = 200
    200,000,000
    limit 5s ???????????????OK
    """
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    M = map(int, input().split())

    for m in M:
        if solve(m, A, n):
            print("yes")
        else:
            print("no")


def solve(m, A, n):
    for b in f(n):
        s = sum(a * bit for a, bit in zip(A, b))
        if m == s:
            return True

    return False


def f(n):
    for i in range(2 ** n):
        # 0/1???n??????????????????bit????????¨
        # 0b ?????????
        bit = bin(i)[2:]
        yield map(int, bit.zfill(n))

if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import product


def main():
    """
    2^20 = 1,048,576
    q = 200
    200,000,000
    limit 5s ???????????????OK
    """
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    M = map(int, input().split())

    dp(n, A, q, M)


def combination(n, A, q, M):
    for m in M:
        if m == 0 or solve(m, A, n):
            print("yes")
        else:
            print("no")


def dp(n, A, q, M):
    M_max = 2000
    _dp = [False] * (M_max + 1)
    for a in A:
        # ?°??????????????????????????????¨????????????????????±?????????(a???2????¶?????????¨?????????)
        for i in range(M_max, 0, -1):
            if _dp[i] and i + a <= M_max:
                _dp[i + a] = True
        # ???????¨????????????¨????????°?????¨????¨±????????????????????¨??§
        _dp[a] = True

    for m in M:
        if _dp[m]:
            print("yes")
        else:
            print("no")


def solve(m, A, n):
    # for b in f1(n):
    for b in product([0, 1], repeat=n):
        s = sum(a * bit for a, bit in zip(A, b))
        if m == s:
            return True

    return False


def f1(n):
    for i in range(2 ** n):
        # 0/1???n??????????????????bit????????¨
        # 0b ?????????
        bit = bin(i)[2:]
        yield map(int, bit.zfill(n))

if __name__ == '__main__':
    main()
n=int(input())
a=[int(i) for i in input().split()]
od=[i for i in a if a%2]
print('YES' if len(od)%2==0 else 'NO')

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
od=[i for i in a if i%2]
print('YES' if len(od)%2==0 else 'NO')
from bisect import bisect
from bisect import insort
 
X,N=list(map(int,input().split()))
if N != 0:
	p=list(map(int,input().split()))
 
	not_list=[]
	for i in range(1,101):
		if i not in p and i != X:
			not_list.append(i)
 
	a=bisect(not_list,X)
	insort(not_list,X)
 
	ans1=not_list[a]-not_list[a-1]
	ans2=not_list[a+1]-not_list[a]
 
	if ans1 < ans2:
		print(not_list[a-1])
	elif ans1 == ans2:
		print(not_list[a-1])
	else:
		print(not_list[a+1])
            
else:
	print(X)


### FIXED CODE ###

X, N = map(int, input().split())
p = list(map(int, input().split()))

p = set(p)
for i in range(200):
    if X - i not in p:
        print(X - i)
        break
    if X + i not in p:
        print(X + i)
        break
import math
N,Y=map(int,input().split())
YY=min(N,math.floor(Y/10000))
flag=False
for i in reversed(range(YY+1)):
    Y2=Y-i*10000
    N2=N-i
    YYY=min(N2,math.floor(YY2/5000))
    for j in reversed(range(YYY+1)):
        YY3=int((Y2-j*5000)/1000)
        if YY3==N2-j:
            print(i, j, YY3)
            flag=True
            break
        else:
            continue
if flag==False:
    print("-1 -1 -1")
else:
    exit()

### FIXED CODE ###

N,Y=map(int,input().split())
flag=False
for i in range(N+1):
    if flag==True:
        break
    else:
        pass
    for j in range(N+1-i):
        k=N-i-j
        if 10000*i+5000*j+1000*k==Y:
            print(i, j, k)
            flag=True
            break
        else:
            continue
if flag==False:
    print("-1 -1 -1")
else:
    pass
print(S,T)

### FIXED CODE ###

S,T = input().split()
print(T,S, sep='')
from collections import defaultdict as dd
from collections import deque
import collections as col
d=dd(list)
q=deque([])

N,M=map(int, input().split())
for _ in range(M):
    f=0
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)
chk=[0]*N
chk[0]=1
temp=1
a=0
while a<N:
    for i in range(len(d[temp])):
        chk[d[temp][i]-1]=1
        q.append(d[temp][i])

    if len(q)>0:
        while a<N:
            if chk[a]==0:
                q.append(a+1)
            a+=1
    else:
        temp=q.pop()

ans=0
for i in  range(N):
    ans=max(ans,len(col.Counter(d[i]))+1)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
        rank[a]=rank[b]
    else:
        par[b]=a
        rank[a]+=rank[b]
        rank[b]=rank[a]

    return

def chk(a,b):
    if par[a]==par[b]:
        print('Yes')
    else:
        print('No')

    return

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

par=(list(range(N+1)))
rank=[1]*(N+1)

for _ in range(M):
    A,B=map(int, input().split())
    union(A,B)

print(max(rank))
a,b,k = map(int,input().split())

A = []
B = []
for i in range(1,a):
    if a % i == 0:
        A.append(i)
for i in range(1,b):
    if b % i == 0:
        B.append(i)
common = list(set(A) & set(B))
common.sort()
print(common[k-1])

### FIXED CODE ###

a,b,k = map(int,input().split())

A = []
B = []
for i in range(1,a+1):
    if a % i == 0:
        A.append(i)
for i in range(1,b+1):
    if b % i == 0:
        B.append(i)
common = list(set(A) & set(B))
common.sort(reverse=True)

print(common[k-1])
a=int(input())
print(a*a)

### FIXED CODE ###

a = input().split(" ")
if int(a[0]) <= 9 and int(a[1]) <= 9:
  print(int(a[0])*int(a[1]))
else:
  print(-1)
import math
a,b,c,d = map(int,input().split())
count_c = 0
count_d = 0
count_cd = 0
count = 0
j = 1
g = c*d//math.gcd(c,d)
for i in range(a,b+1):
    if c*j <= b and c*j>=a:
        count_c += 1
    if d*j <=b and d*j >= a:
        count_c += 1
    if g*j <=b and g*j >= a:
        count_cd += 1
    j += 1
s = count_c+count_d-count_cd
print(b-a +1-s)

### FIXED CODE ###

import fractions
a,b,c,d = map(int,input().split())
count_c = 0
count_d = 0
count_cd = 0
count = 0
j = 1
g = c*d//fractions.gcd(c,d)

count_c = b//c - (a-1)//c
count_d = b//d - (a-1)//d
count_cd = b//g -(a-1)//g
count_s = count_c+count_d-count_cd
print(b-a+1-count_s)
from math import gcd

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

L = [-1] * (N-1)
L[0] = A[0]
R = [-1] * (N-1)
R[0] = A[-1]

for i in range(1, N-1):
    L[i] = gcd(L[i-1], A[i])
    R[i] = gcd(R[i-1], A[-i-1])

ans = 0
for i in range(1, N-1):
    tmp = gcd(L[i-1], R[N-i-2])
    ans = max(ans, tmp)

ans = max(ans, L[N-2])
ans = max(ans, R[N-2])
print(ans)


### FIXED CODE ###

#ABC-125-C
N = int(input())
A = list(map(int, input().split())) #[0, 1, 2, ..., N-2, N-1]
L = [0] * N #L[0]とL[N-1]は0から変わらない。N=5なら実行終了時にL=[*0*,a,b,c,*0*]となる。
R = [0] * N #R[0]とR[N-1]は0から変わらない。N=5なら実行終了時にR=[*0*,f,e,d,A[4]]となる。

def gcd(x, y):
    while y:
        x, y = y, x%y
    return x

ans_gcd = -1

#Lから埋める
L[0] = A[0]
check_gcd = L[0]
for i in range(1, N-1): #N=5のときはi=1~3を実施して最終的にL=[0,a,b,c,0]となる。
    check_gcd = gcd(check_gcd, A[i])
    L[i] = check_gcd

#Rを埋める
R[-1] = A[-1]
check_gcd = R[-1]
for i in reversed(range(1, N-1)):#N=5のときはi=3~1を実施して最終的にR=[0,f,e,d,0]となる。
    check_gcd = gcd(check_gcd, A[i])
    R[i] = check_gcd

#端以外を書き換えの対象とした場合の最大公約数のMaxを探す。
for i in range(1, N-1):
    m = gcd(L[i-1], R[i+1])
    ans_gcd = max(ans_gcd, m)

#端と比べて最終的な答えを出す。N>2のときは数字が低い方を消すだけ。
if N > 2:
    ans_gcd = max(ans_gcd, gcd(A[-2], L[N-3]), gcd(A[1], R[2]))
else:
    ans_gcd = max(A)

print(ans_gcd)
N = input()
a = [input() for i in range(N)]
a.reverse()
print(a)

### FIXED CODE ###

n = int(input())
print(" ".join(input().split()[::-1]))
#python3.4
def inpul(): return list(map(int, input().split()))

N, M = inpul()
X = inpul()

if(N >= M):
    print(0)

new_list = sorted(X)
diff_list = [new_list[i+1] - new_list[i] for i in range(M-1)]
new_dif_list = sorted(diff_list, reverse = True)
else:
  if(N  >= 2):
      for i in range(N-1):
          new_dif_list.pop(0)

  print(sum(new_dif_list))


### FIXED CODE ###

#python3.4
def inpul(): return list(map(int, input().split()))

N, M = inpul()
X = inpul()
new_list = sorted(X)
diff_list = [new_list[i+1] - new_list[i] for i in range(M-1)]
new_dif_list = sorted(diff_list, reverse = True)

if(N >= M):
    print(0)

else:
  if(N  >= 2):
      for i in range(N-1):
        new_dif_list.pop(0)

  print(sum(new_dif_list))
n=int(input())
def di(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
li=di(n)
a=li[-1]
b=li[-2]
print(max(len(str(a)),len(str(b))))

### FIXED CODE ###

n=int(input())
def di(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
li=di(n)
a=li[-1]
if a**2==n:
    print(len(str(a)))
elif n==1:
    print(1)
else:
    b=li[-2]
    print(max(len(str(a)),len(str(b))))
import sys
input = lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
sys.setrecursionlimit(10**7)

def solve(k, cnt):  
    S = str(bin(k)).count("1") 
    L = k % S
    if L == 0:
        return 1
    cnt += solve(L,cnt)
    return cnt 

N = int(input())
P = input()
Df = int(P,2)
for i in range(N-1):
    cnt = 1
    if P[i] == "1":
        tmp = Df - 2**(N-i-1)
    else:
        tmp = Df + 2**(N-i-1)    
    #print(tmp, bin(tmp))
    print(solve(tmp,cnt))
    
cnt = 1
if P[-1] == "1":
    tmp = Df - 1
else:
    tmp = Df + 1
print(solve(tmp,cnt))
#print(solve(N,cnt))

### FIXED CODE ###

N = int(input())
x = input()

cnt_x = x.count("1")
px10 = 0
nx10 = 0
ans = [0] * (N+1)

for i in range(1, N+1): #Nまで先に出しておく
    popcnt = format(i,"b").count("1")
    fx = i % popcnt
    ans[i] = ans[fx] + 1

for i in range(N):
    px10 += (int(x[i]) * pow(2,N-1-i, cnt_x+1)) % (cnt_x+1)#0⇒1となった場合の合計
    if cnt_x != 0 and cnt_x != 1:
        nx10 += int(x[i])*pow(2,N-1-i,cnt_x-1) % (cnt_x-1)#1⇒0となった場合の合計
#print(px10)
#print(nx10)
for i in range(N):
    if x[i] == "0":
        xi10 = (px10+pow(2,N-1-i,cnt_x+1))%(cnt_x+1)
        print(ans[xi10]+1)
    else:
        if cnt_x != 1:
            xi10 = (nx10-pow(2,N-1-i,cnt_x-1))%(cnt_x-1)
            print(ans[xi10]+1)
        else:
            print(0)
import bisect

n,m,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
sum_a=[a[0]]
for i in range(len(a)-1):
    sum_a.append(sum_a[i]+a[i+1])
sum_b=[b[0]]
for i in range(len(b)-1):
    sum_b.append(sum_b[i]+b[i+1])

#現在のインデックス
idx_a=0
idx_b=0

while idx_a<n or idx_b<m:
    read=''
    #aの読める数
    oset_a=sum_a[idx_a-1] if idx_a>0 else 0
    can_cnt_a=bisect.bisect_right(sum_a,k+oset_a)
    #bの読める数
    oset_b=sum_b[idx_b-1] if idx_b>0 else 0
    can_cnt_b=bisect.bisect_right(sum_b,k+oset_b)
    read='a' if can_cnt_a-idx_a>can_cnt_b-idx_b else 'b'
    

    #読むほうをPOP
    k-=a[idx_a] if read=='a' else b[idx_b]
    #kを超えた場合ブレーク
    if k<0:
        break
    #カウントアップ
    if read=='a':
        idx_a+=1
    else:
        idx_b+=1
print(idx_a+idx_b)


### FIXED CODE ###

import bisect

n,m,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
sum_a=[a[0]]
for i in range(len(a)-1):
    sum_a.append(sum_a[i]+a[i+1])
sum_b=[b[0]]
for i in range(len(b)-1):
    sum_b.append(sum_b[i]+b[i+1])

#現在のインデックス
idx_a=0
idx_b=0

while idx_a<n or idx_b<m:
    read=''
    #aの読める数
    oset_a=sum_a[idx_a-1] if idx_a>0 else 0
    can_cnt_a=bisect.bisect_right(sum_a,k+oset_a)
    #bの読める数
    oset_b=sum_b[idx_b-1] if idx_b>0 else 0
    can_cnt_b=bisect.bisect_right(sum_b,k+oset_b)
    read='a' if can_cnt_a-idx_a>can_cnt_b-idx_b else 'b'
    if idx_a==n:
        read='b'
    if idx_b==m:
        read='a'
    

    #読むほうをPOP
    k-=a[idx_a] if read=='a' else b[idx_b]
    #kを超えた場合ブレーク
    if k<0:
        break
    #カウントアップ
    if read=='a':
        idx_a+=1
    else:
        idx_b+=1
print(idx_a+idx_b)
import heapq
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
d=[int(input()) for i in range(q)]
L1=[]
for i in range(n):
  L1.append([l[i][0]-l[i][2],1,l[i][2]])
  L1.append([l[i][1]-l[i][2],-1,l[i][2]])
L1.sort()
L2=[]
heapq.heapify(L2)
L3=[]
L3=set(L2)
ctd=0
for i in range(len(L1)):
  while L1[i][0]>d[ctd]:
    if len(L2)!=0:
      print(heapq.heappop(L2))
    else:
      print(-1)
    ctd+=1
  if L1[i][1]==1:
    heapq.heappush(L2,L1[i][2])
    L3.add(L1[i][2])
  else:
    L3.remove(L1[i][2])
while ctd<q:
  print(-1)
  ctd+=1

### FIXED CODE ###

import sys
input=sys.stdin.readline
import heapq
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
L1=[]
for i in range(n):
  L1.append((l[i][0]-l[i][2],1,l[i][2]))
  L1.append((l[i][1]-l[i][2],-1,l[i][2]))
for i in range(q):
  L1.append((int(input()),2,0))
L1.sort()
L2=[]
heapq.heapify(L2)
L3=[]
L3=set(L3)
for i in range(len(L1)):
  if L1[i][1]==1:
    heapq.heappush(L2,L1[i][2])
    L3.add(L1[i][2])
  elif L1[i][1]==-1:
    L3.remove(L1[i][2])
  else:
    while L2 and L2[0] not in L3:
      heapq.heappop(L2)
    if L2:
      print(L2[0])
    else:
      print(-1)
# -*- coding: utf-8 -*-

class Combination_with_repetition():
    def getPattern(self, arr :list, r :int) -> list:
        self._selected=[]
        self._all_pattern=[]
        
        self._make(arr,r)
        return self._all_pattern
        
    def _make(self, arr :list, r :int):
        if r == 0:
            self._all_pattern.append(self._selected[:])
            return 
        
        for i in range(len(arr)):
            self._selected.append( arr[i] )
            self._make(arr[i:],r-1)
            
            self._selected.pop()  # Backtracking

#-----
N,M,Q = list(map(int, input().rstrip().split()))
abcd_list = [list(map(int, input().rstrip().split())) for i in range(Q)]

#-----
comb_rep = Combination_with_repetition()
pattern = comb_rep.getPattern( list(range(1, M+1)) , M)


max_sum = 0

for pat in pattern:
    tmp_sum = 0
    
    for a,b,c,d in abcd_list:
        if ( pat[b-1] - pat[a-1] ) == c:
            tmp_sum += d
    
    max_sum = max(max_sum, tmp_sum)

print(max_sum)


### FIXED CODE ###

# -*- coding: utf-8 -*-

class Combination_with_repetition():
    def getPattern(self, arr :list, r :int) -> list:
        self._selected=[]
        self._all_pattern=[]
        
        self._make(arr,r)
        return self._all_pattern
        
    def _make(self, arr :list, r :int):
        if r == 0:
            self._all_pattern.append(self._selected[:])
            return 
        
        for i in range(len(arr)):
            self._selected.append( arr[i] )
            self._make(arr[i:],r-1)
            
            self._selected.pop()  # Backtracking

#-----
N,M,Q = list(map(int, input().rstrip().split()))
abcd_list = [list(map(int, input().rstrip().split())) for i in range(Q)]

#-----
comb_rep = Combination_with_repetition()
pattern = comb_rep.getPattern( list(range(1, M+1)) , N)


max_sum = 0

for pat in pattern:
    tmp_sum = 0
    
    for a,b,c,d in abcd_list:
        if ( pat[b-1] - pat[a-1] ) == c:
            tmp_sum += d
    
    max_sum = max(max_sum, tmp_sum)

print(max_sum)
# C - Forbidden List

x, n = map(int,input().split())
P = list(map(int,input().split()))

t = -100
a = [0]*100
for p in P:
    a[p-1] = 1

d = 0
while True:
    if a[x-1-d] == 0:
        t = x-d
        break
    elif a[x-1+d] == 0:
        t = x + d
        break
    else:
        d += 1

print(t)


### FIXED CODE ###

# C - Forbidden List

x, n = map(int,input().split())
P = list(map(int,input().split()))

t = -100
a = [0]*300
for p in P:
    a[100+p-1] = 1

d = 0
while True:
    if a[100+x-1-d] == 0:
        t = x-d
        break
    elif a[100+x-1+d] == 0:
        t = x + d
        break
    else:
        d += 1

print(t)
import sys
N=int(input())
a=list(map(int,input().split()))
b,c,d=0,1,0
while True:
    while True:
        e==2**c
        if a[b]%(e)>=e/2:
            d+=1
        b+=1
        if b==N:
            if d%2==1:
                print('No')
                sys.exit()
            else:
                break
    b,d=0,0
    c+=1
    if c==27:
        break
print('Yes')

### FIXED CODE ###

import sys
N=int(input())
a=list(map(int,input().split()))
b,c,d=0,1,0
while True:
    while True:
        if a[b]%(2**c)>=2**(c-1):
            d+=1
        b+=1
        if b==N:
            if d%2==1:
                print('No')
                sys.exit()
            else:
                break
    b,d=0,0
    c+=1
    if c==27:
        break
print('Yes')
using namespace std;
int main(){
int a,b,c,d;
cin >>a>>b>>c>>d;
if(abs(a-c)<=d || (abs(a-b)<=d && abs(b-c)<=d)) puts("Yes");
else puts("No");

### FIXED CODE ###

a, b, c, d = map(int, input().split())

if d >= abs(a - c) or (d >= abs(a - b) and d >= abs(b - c)):
    print('Yes')
else:
    print('No')
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N=int(input())
    A=sorted(list(map(int,input().split())))

    l=[0]*(10**6+1)

    for i in A:
        if l[i+1]!=0:
            l[i+1]+=1
            continue
        for j in range(1,10**6//i):
            l[j*i+1]+=1
    
    cnt=0
    for i in A:
        if l[i+1]<=1:
            cnt+=1
    print(cnt)




    
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N=int(input())
    A=sorted(list(map(int,input().split())))

    l=[0]*(10**6+5)

    for i in A:
        if l[i]!=0:
            l[i]+=1
            continue
        for j in range(i,10**6+5,i):
            l[j]+=1
    
    cnt=0
    for i in A:
        if l[i]==1:
            cnt+=1
    print(cnt)




    
resolve()