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

from collections import deque

N, M = map(int, input().split())
v = [[] for _ in range(N)]
p = [True] * N
for _ in range(N + M - 1) :
    A, B = map(int, input().split())
    v[A-1].append(B-1)
    p[B-1] = False
    
s = p.index(True)
dist = [0] * N
par = [-1] * N

q = deque([s])
while q :
    cur = q.popleft()
    for nex in v[cur] :
        if dist[cur] + 1 > dist[nex] :
            dist[nex] = dist[cur] + 1
            par[nex] = cur
            q.append((nex))

for i in range(N) :
    print(par[i] + 1)

### FIXED CODE ###

N, M = map(int, input().split())
v = [[] for _ in range(N)]
u = [[] for _ in range(N)]
for _ in range(N + M - 1) :
    A, B = map(int, input().split())
    v[A-1].append(B-1)
    u[B-1].append(A-1)

for i in range(N) :
    if len(u[i]) == 0 :
        s = i
        break
        
dist = [0] * N
par = [-1] * N
cnt = [0] * N

par[s] = -1
q = [s]
while q :
    cur = q.pop()
    cnt[cur] += 1
    if cur != s and cnt[cur] != len(u[cur]) :
        continue
        
    for nex in v[cur] :
        if dist[cur] + 1 > dist[nex] :
            dist[nex] = dist[cur] + 1
            par[nex] = cur
            q.append((nex))

for i in range(N) :
    print(par[i] + 1)
### BUGGY CODE ###

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

d=sorted(d)
ans=0
 
for i in range(10**7):
    if d[int(N/2-1)] < i and i <= d[int(N/2)]:
        ans +=1
 
print(ans)

### FIXED CODE ###

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

d=sorted(d)
ans= d[int(N/2)] - d[int(N/2-1)]

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

import itertools
N,K = map(int,input().split())
P = list(map(int,input().split()))
Sigmas = []
for M in itertools.combinations(P,K):
    Sigma = sum(list(M))
    Sigmas.append(Sigma)
print(min(Sigmas))


### FIXED CODE ###

import itertools
N,K = map(int,input().split())
P = list(map(int,input().split()))
Sigma = sorted(P,reverse = False)
print(sum(Sigma[:K]))
### BUGGY CODE ###

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

## 高々 N(N-1)/2　< 2 * 10^10 のため何とかなる...?
mod = 10**9 + 7

sum = 0
for i in range(N-1):
    for j in range(i+1,N):
        sum += a[i]*a[j]

ans = sum % mod
print(ans)

### FIXED CODE ###

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

## 高々 N(N-1)/2　< 2 * 10^10 のため何とかなる...?
mod = 10**9 + 7

'''
sum = 0
for i in range(N-1):
    for j in range(i+1,N):
        sum += a[i]*a[j]

ans = sum % mod
print(ans)
'''

### a1　は a2~an(= S)までの和を必要とする. a2 は S - a2 (=S). a3 は S - a3...

s = 0
for i in range(N):
    s += a[i]

sum = 0
for i in range(N-1):
    s -= a[i]
    sum += a[i]*s

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

from itertools import accumulate
import sys
N, K = map(int, input().split())
An = list(map(int, input().split()))

for cnt in range(K):
    tmp = [0]*(N+1)
    for i in range(N):
        power = An[i]
        left = max(0, i-power)
        right = min(N, i+power+1)
        tmp[left] += 1
        tmp[right] -= 1
    An = list(accumulate(tmp))[:-1]
    if cnt > 40:
        An = [N]*N
        print(*An)
        sys.exit()
print(*An)


### FIXED CODE ###

from itertools import accumulate
import sys
N, K = map(int, input().split())
An = list(map(int, input().split()))

for cnt in range(K):
    tmp = [0]*(N+1)
    for i in range(N):
        power = An[i]
        left = max(0, i-power)
        right = min(N, i+power+1)
        tmp[left] += 1
        tmp[right] -= 1
    An = list(accumulate(tmp))[:-1]
    if cnt > 40:
        An = [N]*N
        print(*An)
        sys.exit()
print(*An)
### BUGGY CODE ###

B,W = map(int, input().split())
N = B+W

factorial = [1]
for i in range(N+1):
    factorial.append( factorial[-1] * (i+1))
# print(factorial)

mod = 10**9+7

de_factorial = [0] * (N+1)
de_factorial[N] = pow(  factorial[N] , mod-2, mod  )

for i in range( N, 0, -1):
    de_factorial[i-1] = de_factorial[i] * i

# print(de_factorial)

def comb(n,r):
    if n < r: return 0
    if n == r: return 1
    return (factorial[n] * de_factorial[r] * de_factorial[n-r]) % mod


p = [0] * (N+1) # Bを食べきった確率
q = [0] * (N+1) # Wを食べきった確率

de2 = de_factorial[2]


# print(p)
# print(q)
for i in range(1, N+1):
    p[i] = p[i-1] + comb(i-1 ,B-1) * de2 % mod 
    q[i] = q[i-1] + comb(i-1 ,W-1) * de2  % mod 
    de2 = de2 * de_factorial[2] % mod

    tmp = 0
    tmp = ( q[i-1] + 1-p[i-1] ) * de_factorial[2] % mod
    

    print(tmp % mod)

### FIXED CODE ###

B,W = map(int, input().split())
N = B+W
mod = 10**9+7

factorial = [1]
for i in range(N+1):
    factorial.append( factorial[-1] * (i+1) % mod)
# print(factorial)



de_factorial = [0] * (N+1)
de_factorial[N] = pow(  factorial[N] , mod-2, mod  )

for i in range( N, 0, -1):
    de_factorial[i-1] = de_factorial[i] * i % mod
    
def comb(n,r):
    if n < r: return 0
    if n == r: return 1
    return (factorial[n] * de_factorial[r] * de_factorial[n-r]) % mod


p = [0] * (N+1) # Bを食べきった確率
q = [0] * (N+1) # Wを食べきった確率

de2 = de_factorial[2]
for i in range(1, N+1):
    p[i] = p[i-1] + comb(i-1 ,B-1) * de2 % mod 
    q[i] = q[i-1] + comb(i-1 ,W-1) * de2  % mod 
    de2 = de2 * de_factorial[2] % mod

    tmp = ( q[i-1] + 1-p[i-1] ) * de_factorial[2] % mod
    
    print(tmp)
### BUGGY CODE ###

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

l = []
for i in range(1, n + 1):
    l.append([a[i - 1], i])

l.sort()

res = str(l[0][1])
for i in range(1, n):
    res = res + " " + str(l[i][1])
print(res)


### FIXED CODE ###

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

l = []
for i in range(1, n + 1):
    l.append([a[i - 1], i])

l.sort()

print(" ".join([str(l[i][1]) for i in range(0, n)]))
### BUGGY CODE ###

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

seq = [int(i) for i in input().split()]

ans = 0

for i in range(N-1):
    if seq[i+1] != 0:
        while seq[i] + seq[i+1] > x and seq[i+1] != 0:
            seq[i+1] -= 1
            ans += 1

    if seq[i] + seq[i+1] > x:
        while seq[i] + seq[i+1] > x:
            seq[i] -= 1
            ans += 1

print(ans)

### FIXED CODE ###

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

seq = [int(i) for i in input().split()]

ans = 0

for i in range(N-1):
    if seq[i]+seq[i+1] > x:
        dec = seq[i]+seq[i+1] - x
        if seq[i+1] > dec:
            seq[i+1] = seq[i+1] - dec
        else:
            seq[i+1] = 0
            seq[i] = seq[i] - dec + seq[i+1]
        ans += dec

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

import sys
import bisect
import heapq
sys.setrecursionlimit(10 ** 7)

# TLE

N, Q = map(int, input().split())
STX = [[int(x) for x in input().split()] for _ in range(N)]
EVENT = []
for s, t, x in STX:
    EVENT.append((s-x, 1, x))
    EVENT.append((t-x, 0, x))

for i in range(Q):
    d = int(input())
    EVENT.append((d, 2, i))

ans = [-1] * Q

EVENT.sort()

# print(EVENT)

STOP = set()
h = []
for t, op, x in EVENT:
    if op == 2 and STOP:
        while h[0] not in STOP:
            heapq.heappop(h)
        ans[x] = h[0]
    elif op == 1:
        STOP.add(x)
        heapq.heappush(h, x)
    elif op == 0:
        STOP.remove(x)


print("\n".join(map(str, ans)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

def gcd(m,n) :
    x = max(m,n)
    y = min(m,n)
    if x%y == 0 :
        return y
    else :
        while x%y != 0 :
            z = x%y
            x = y
            y = z
        else :
            return z

def lcm(m,n) :
    return int(m*n/gcd(m,n))

N,M = map(int,input().split())
S = list(input())
T = list(input())
L = lcm(N,M)
A = []
B = []
flag = 0
counter = 0
for i in range(N) :
    A.append(i*L//N+1)
for j in range(M) :
    b = j*L//M+1
    if b in A :
        index = N*j//M
        if S[index] == T[j] :
            counter += 1
        else :
            flag = 1
    else :
        counter += 1
if flag == 1 :
    print(-1)
else :
    if counter == M :
        print(L)

### FIXED CODE ###

def gcd(m,n) :
    x = max(m,n)
    y = min(m,n)
    if x%y == 0 :
        return y
    else :
        while x%y != 0 :
            z = x%y
            x = y
            y = z
        else :
            return z

def lcm(m,n) :
    return int(m*n/gcd(m,n))

N,M = map(int,input().split())
S = list(input())
T = list(input())
L = lcm(N,M)
A = []
B = []
flag = 0
counter = 0
if N >= M :
    for i in range(N) :
        A.append(i*L//N+1)
    for j in range(M) :
        b = j*L//M+1
        if j*N % M == 0 :
            index = N*j//M
            if S[index] == T[j] :
                counter += 1
            else :
                flag = 1
                break
        else :
            counter += 1
    if flag == 1 :
        print(-1)
    else :
        if counter == M :
            print(L)
else :
    for i in range(M) :
        A.append(i*L//M+1)
    for j in range(N) :
        b = j*L//N+1
        if j*M % N == 0 :
            index = M*j//N
            if T[index] == S[j] :
                counter += 1
            else :
                flag = 1
                break
        else :
            counter += 1
    if flag == 1 :
        print(-1)
    else :
        if counter == N :
            print(L)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([I() for _ in range(n)])
    d = collections.defaultdict(lambda: inf)
    x = 0
    for c in a:
        x ^= c
    d[x] = 0
    for c in a:
        c1 = c ^ (c-1)
        e = {}
        for k,v in list(d.items()):
            if d[k^c1] > v + 1:
                e[k^c1] = v + 1
        for k,v in e.items():
            d[k] = v

    if d[0] == inf:
        return -1

    return d[0]




print(main())



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([I() for _ in range(n)])
    x = 0
    for c in a:
        x ^= c
    s = set()
    for c in a:
        s.add(c ^ (c-1))

    r = 0
    for c in sorted(s, reverse=True):
        cb = bin(c)
        xb = bin(x)
        if len(cb) == len(xb) and x > 0:
            x ^= c
            r += 1

    if x != 0:
        return -1

    return r




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

import sys

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

exp={}

ans=0
cnt=0
for i in range(1,1001):
    sum=0
    for j in range(1,i+1):
        sum+=j
    exp[i]=sum/i

for j in range(n-k+1):
    tmp=0
    for i in range(k):
        tmp+=exp[p[i+cnt]]
    if ans < tmp:
        ans=tmp
    cnt += 1

print(ans)


### FIXED CODE ###

from itertools import accumulate

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

exp={}
cum=[]

ans=0
cnt=0
for i in range(1,1001):
    sum=0
    for j in range(1,i+1):
        sum+=j
    exp[i]=sum/i

for i in p:
    cum.append(exp[i])

cumsum=list(accumulate(cum))
cumsum.insert(0,0)

for i in range(n-k+1):
    tmp = cumsum[i+k] - cumsum[i]
    if ans <= tmp:
        ans = tmp

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

from collections import deque

INF = 10 ** 9

H, W = map(int, input().split())
Ch, Cw = map(lambda x:int(x)-1, input().split())
Dh, Dw = map(lambda x:int(x)-1, input().split())
S = [list(map(lambda x: INF if x == "." else -1, [c for c in input()])) for _ in range(H)]


"""h = []
heapq.heappush(h, (0, Ch, Cw))"""

q = deque()
q.append((0, Ch, Cw))
S[Ch][Cw] = 0

while len(q) != 0:
    d, nh, nw = q.popleft()
    if nh == Dh and nw == Dw:
        print(d)
        exit()

    for dh in [-2, -1, 0, 1, 2]:
        for dw in [-2, -1, 0, 1, 2]:
            flag = False
            if dh == 0 and dw == 0:
                continue
            newd = d + 1
            if abs(dh) + abs(dw) == 1:
                newd = d
                flag = True
            newh = nh + dh
            neww = nw + dw
            if 0 <= newh < H and 0 <= neww < W:
                if S[newh][neww] > newd:
                        S[newh][neww] = newd
                        if flag:
                            q.appendleft((newd, newh, neww))
                        else:
                            q.append((newd, newh, neww))   
print(-1)


### FIXED CODE ###

from collections import deque

INF = 10 ** 9

H, W = map(int, input().split())
Ch, Cw = map(lambda x:int(x)-1, input().split())
Dh, Dw = map(lambda x:int(x)-1, input().split())
S = [list(map(lambda x: INF if x == "." else -1, [c for c in input()])) for _ in range(H)]


"""h = []
heapq.heappush(h, (0, Ch, Cw))"""

q = deque()
q.append((0, Ch, Cw))
S[Ch][Cw] = 0

while len(q) != 0:
    d, nh, nw = q.popleft()
    if nh == Dh and nw == Dw:
        print(d)
        exit()

    for dh in [-2, -1, 0, 1, 2]:
        for dw in [-2, -1, 0, 1, 2]:
            flag = False
            if dh == 0 and dw == 0:
                continue
            newd = d + 1
            if abs(dh) + abs(dw) == 1:
                newd = d
                flag = True
            newh = nh + dh
            neww = nw + dw
            if 0 <= newh < H and 0 <= neww < W:
                if S[newh][neww] > newd:
                        S[newh][neww] = newd
                        if flag:
                            q.appendleft((newd, newh, neww))
                        else:
                            q.append((newd, newh, neww))   
print(-1)
### BUGGY CODE ###

N = int(input())
S = input().rstrip()

ans = []
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            key = S[i] + S[j] + S[k]
            if key not in ans:
                ans.append(key)
print(len(ans))

### FIXED CODE ###

N = int(input())
S = input().rstrip()

ans = 0
for i in range(1000):
    a = ('00' + str(i))[-3:]
    try:
        j = S.index(a[0])
    except ValueError:
        continue
    try:
        k = S.index(a[1], j+1)
    except ValueError:
        continue
    try:
        l = S.index(a[2], k+1)
    except ValueError:
        continue
    ans += 1
print(ans)
### BUGGY CODE ###

s=input()
n=len(s)
mod=10**9+7
dp=[13*[0]for _ in range(n)]
if s[0]=="?":dp[0]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
else:dp[0][int(s[0])]=1
for i in range(1,n):
  if s[i]!="?":
    k=int(s[i])
    for j in range(13):dp[i][(j*10+k)%13]+=dp[i-1][j]
  else:
    for j in range(13):
      for k in range(10):dp[i][(j*10+k)%13]+=dp[i-1][j]
  for j in range(13):dp[i][j]%=mod
print(dp[-1][5])

### FIXED CODE ###

s=input()
n=len(s)
dp=[13*[0]for _ in range(n)]
if s[0]=="?":dp[0]=10*[1]+[0]*3
else:dp[0][int(s[0])]+=1
for i in range(1,n):
  if s[i]!="?":
    for j in range(13):
      dp[i][(j*10+int(s[i]))%13]=dp[i-1][j]
  else:
    for j in range(13):
      for k in range(10):
        dp[i][(j*10+k)%13]+=dp[i-1][j]
  for j in range(13):dp[i][j]%=10**9+7
print(dp[-1][5])
### BUGGY CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            if i+v+1<n:
                b[i+v+1]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

if '__main__' == __name__:
    main()

### FIXED CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

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

x1 = input()
x2 = [int(s) for s in input().strip().split(" ") ]
 
if len(x2) >0 :
   result =  1
else :
   result =  0

for x in x2:
   result *= x 

if 10**18 < result :
 print("-1")
else:
 print(result) 


### FIXED CODE ###

x1 = input()
x2 = [int(i) for i in input().split(" ")]

result = 0
if 0 in x2:
  None 
else:
  result = 1
  for xv in x2:
     result = xv * result
  
     if 10**18 < result : 
        result = -1
        break


print(result)
### BUGGY CODE ###

N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        for k in range(Qlist[i][0],Qlist[i][1]+1):
            if j <= k:
                if p[j-1][k-1] != 0:
                    q = q+ p[j-1][k-1]
    print(q)

### FIXED CODE ###

N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if i == 0:
            r[i][j] = p[i][j] + r[i][j-1]      
        elif j == 0:
            r[i][j] = p[i][j] +r[i-1][j]
        else:
            r[i][j] = r[i-1][j] + r[i][j-1] - r[i-1][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    if Qlist[i][0] == 1:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1]
    else:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1] - r[Qlist[i][0]-2][Qlist[i][1]-1]
    print(b)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush
import numpy as np

def main():
    input = sys.stdin.readline
    INF = 10**15
    ans = INF
    N, M = map(int, input().split())
    heap = []
    for _ in range(M):
        l, r, c = map(int, input().split())
        heappush(heap, (l-1, r-1, c))
    
    dp = np.array([INF]*N, dtype=int)
    dp[0] = 0

    while heap:
        l, r, c = heappop(heap)
        s = dp[l]
        d = np.where(dp[l+1:r+1] < s+c, dp[l+1:r+1], s+c)
        dp[l+1:r+1] = d
            
    if dp[N-1] == INF:
        return -1
    
    return dp[N-1]

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import sys
from heapq import heappop, heappush, heapify

def dijkstra(s, t, links):
    """Dijkstra algorism
    s: int, start node.
    t: int, target node.
    links: iterable, link infomation.
           links[i] contains edges from node i: (cost, target_node).

    return int, minimal cost from s node to t node.
    """
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while len(heap) > 0:
        cost, node = heappop(heap)
        if node == t:
            return cost

        if node in visited:
            continue

        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 in visited:
                continue

            heappush(heap, (cost + cost2, node2))

    return -1

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    links = [[] for _ in range(N)]
    for i in range(1, N):
        links[i].append((0, i-1))

    for _ in range(M):
        l, r, c = map(int, input().split())
        links[l-1].append((c, r-1))
    
    return dijkstra(0, N-1, links)
    

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

from collections import Counter
import math
def solve():
    N = int(input())
    A = list(map(int,input().split()))

    st = set(A)
    counter = Counter(A)

    ans = 0
    for i in range(N):
        if counter[A[i]] >= 2:
            continue
        divisors = calc_divisors(A[i])
        for divisor in divisors:
            if divisor == A[i]:
                continue
            if divisor in st:
                break
        else:
            ans += 1
    
    print(ans)

def calc_divisors(n):
    divisors = []
    for i in range(1,int(math.sqrt(n)+1)):
        if n % i == 0:
            divisors.append(i)
            if (i*i != n):
                divisors.append(n//i)

    return divisors

if __name__ == '__main__':
    solve()

### FIXED CODE ###

from collections import Counter
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    dp = [True] * (10 ** 6 + 1)
    counter = Counter(A)

    A.sort()
    ans = 0
    for a in A:
        if dp[a]:
            if counter[a] == 1:
                ans += 1
            i = a
            while i <= 10 ** 6:
                dp[i] = False
                i += a
    
    print(ans)

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

# -*- coding: utf-8 -*-
import collections
# input
n = int(input())
s = collections.Counter()
for i in range(n):
    s[input()] += 1
# print(s)
# output
# k = c.most_common()[0][1])
#out = collections.OrderedDict(k)
o = list(k for k, v in s.items() if v == s.most_common()[0][1])
for i in sorted(o):
    print(i)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import Counter
# input
n = int(input())
s = []
for i in range(n):
    s.append(input())
c = Counter(s)
# output
ma = c.most_common()[0][1]
o = [k for k, v in c.items() if v == ma]
o.sort()
print('\n'.join(o))
### BUGGY CODE ###

n = int(input())
a_ls = []
for i in range(n):
    a_ls.append(int(input()))
cnt = 0
while len(a_ls) > 0:
    cnt += 1
    L_ls = [a_ls[0]]
    for a in a_ls[1:]:
        if L_ls[-1] < a:
            L_ls.append(a)
    for a in L_ls:
        a_ls.remove(a)
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
a_ls = []
for i in range(n):
    a_ls.append(-int(input()))
L_ls = [a_ls[0]]
for a in a_ls[1:]:
    if L_ls[-1] <= a:
        L_ls.append(a)
    else:
        L_ls[bisect.bisect_right(L_ls, a)] = a
print(len(L_ls))