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

import sys
S = sys.stdin.readlines()

N,Q = map(int, S[0].split())
List = []
for i in S[1:N+1]:
    s, t, x = map(int, i.split())
    List.append([s-0.5-x, 1, x])
    List.append([t-0.5-x, -1, x])
D = []
for i in S[N+1:]:
    D.append(int(i))

import heapq
    
List.sort()

h_in = []
h_ex = []
ans = []
j = 0
for i in range(Q):
    while j < 2*N and List[j][0] < D[i]:
        if List[j][1] == 1:
            heapq.heappush(h_in, List[j][2])
        else:
            heapq.heappush(h_ex, List[j][2])
        j += 1
    while len(h_in) > 0 and len(h_ex) > 0 and h_in[0] == h_ex[0]:
        heapq.heappop(h_in)
        heapq.heappop(h_ex)
    if h_in:
        ans.append(h_in[0])
    else:
        ans.append(-1)
    
for i in range(Q):
    print(ans[i])

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N,Q = map(int, input().split())
List = []
dic = {}
for _ in range(N):
    s, t, x = map(int, input().split())
    List.append((s-0.5-x, 1, x))
    List.append((t-0.5-x, -1, x))
    dic[x] = False

import heapq
    
List.sort()

h = []
j = 0
for _ in range(Q):
    D = int(input())
    while j < 2*N and List[j][0] < D:
        if List[j][1] == 1:
            heapq.heappush(h, List[j][2])
            dic[List[j][2]] = True
        else:
            dic[List[j][2]] = False
        j += 1
    while h:
        ans = h[0]
        if dic[ans]:
            print(ans)
            break
        else:
            heapq.heappop(h)
    if not h:
        print(-1)
### BUGGY CODE ###

from operator import mul
from functools import reduce


def cmb(n, r):
        r = min(n - r, r)
        if r == 0:
                return 1
        elif r < 0:
                return 0
        numer = reduce(mul, range(n, n - r, -1))
        denom = reduce(mul, range(1, r + 1))
        return numer // denom


N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
ans = 0
for si in set(s):
        n = s.count(si)
        ans += cmb(n, 2)
print(ans)


### FIXED CODE ###

from operator import mul
from functools import reduce
import collections


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    elif r < 0:
        return 0
    numer = reduce(mul, range(n, n - r, -1))
    denom = reduce(mul, range(1, r + 1))
    return numer // denom


N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(s)
ans = 0
for si in set(s):
    n = c[si]
    ans += cmb(n, 2)
print(ans)
### BUGGY CODE ###

def main():
  N,M,*alst=map(int, open(0).read().split())
  mod=10**9+7
  dp = [0] * (N+1)
  dp[:2] = [1, 1 if 1 not in alst else 0]
  for i in range(2, N+1):
    if i not in alst:
      dp[i] = (dp[i-2] + dp[i-1])%mod
  print(dp[N])

main()

### FIXED CODE ###

def main():
  N,M,*alst=map(int, open(0).read().split())
  alst=set(alst)
  mod=10**9+7
  dp = [0] * (N+1)
  dp[:2] = [1, 1 if 1 not in alst else 0]
  for i in range(2, N+1):
    if i not in alst:
      dp[i] = (dp[i-2] + dp[i-1])%mod
  print(dp[N])
main()
### BUGGY CODE ###

ans = input()
Q = int(input())
is_reverse = False
for _ in range(Q):
    q = list(map(str,input().split()))
    if q[0] == '1':
        is_reverse = True ^ is_reverse # 反転
        #ans = ans[::-1]
    else:
        if is_reverse: # 反転してた場合
            if q[1] == '1':
                ans = ans + q[2]
            else:
                ans = q[2] + ans
        else:
            if q[1] == '1':
                ans = q[2] + ans
            else:
                ans = ans + q[2]
if is_reverse:
    print(ans[::-1])
else:
    print(ans)
#print(ans)


### FIXED CODE ###

from collections import deque
s = list(input())
ans = deque(s)
Q = int(input())
is_reverse = False
for _ in range(Q):
    q = list(map(str,input().split()))
    if q[0] == '1':
        is_reverse = True ^ is_reverse # 反転
        #ans = ans[::-1]
    else:
        if is_reverse: # 反転してた場合
            if q[1] == '1':
                #ans = ans + q[2]
                ans.append(q[2])
            else:
                #ans = q[2] + ans
                ans.appendleft(q[2])
        else:
            if q[1] == '1':
                #ans = q[2] + ans
                ans.appendleft(q[2])
            else:
                #ans = ans + q[2]
                ans.append(q[2])
ans_s = ''.join(ans)
if is_reverse:
    print(ans_s[::-1])
else:
    print(ans_s)

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

import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].append(b)
  v[b].append(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def input():
  return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].append(b)
  v[b].append(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
for i in range(N):

    if B[i]:
        continue

    else:
        temp=A[i]
        for m in range(i,N):
            if not B[m]:
                if A[m]==C[-1]:
                    B[m]=1
                    C.pop()
                    break
                else:
                    if temp<A[m]:
                        temp=A[m]
                        B[m]=1
        count+=1
    #print(i,count,B)
print(count)


### FIXED CODE ###

import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

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

N, M, Q = map(int,input().split())
m =  [[0 for y in range(N+1)] for x in range(N+1)]
m2 =  [[0 for y in range(N+1)] for x in range(N+1)]

for i in range(M):
    l, r = map(int,input().split())
    m[l][r]+=1

for i in range(1,N+1):
    s=m[i][i]
    m2[i][i]=s
    for j in range(i+1,N+1):
        for k in range(i,j+1):
            s+=m[k][j]
        m2[i][j]=s


for i in range(1,Q+1):
    l, r = map(int,input().split())
    print(m2[l][r])


### FIXED CODE ###

N, M, Q = map(int,input().split())
m =  [[0 for y in range(N+1)] for x in range(N+1)]
m2 =  [[0 for y in range(N+1)] for x in range(N+1)]
m3 =[[0 for y in range(N+1)] for x in range(N+1)]

for i in range(M):
    l, r = map(int,input().split())
    m[l][r]+=1

for j in range(1, N+1):
    s=0
    for i in range(1, N+1):
        s+=m[i][j]
        m2[i][j]=s

for i in range(1, N+1):
    s=0
    for j in range(i, N+1):
        s+=m2[j][j]-m2[i-1][j]
        m3[i][j]=s

for i in range(1,Q+1):
    l, r = map(int,input().split())
    print(m3[l][r])
### BUGGY CODE ###

M=998244353
N=int(input())
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for _ in range(N):
	a=int(input())
	i=s
	while i>=0:
		d[i+a]+=d[i]%M
		d[i]*=2
		e[i+a]+=e[i]%M
		i-=1
	s+=a
	z=z*3%M
for i in range(s+1>>1,s+1):
	z-=d[i]*3
	z%=M
print([(z+e[s//2]*3)%M,z][s%2])


### FIXED CODE ###

M=998244353
N=int(input())
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for _ in range(N):
	a=int(input())
	i=s
	while i>=0:
		d[i+a]+=d[i]%M
		d[i]*=2
		e[i+a]+=e[i]%M
		i-=1
	s+=a
	z=z*3%M
for i in range(s+1>>1,s+1):
	z-=d[i]*3
	z%=M
print([(z+e[s//2]*3)%M,z][s%2])
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
a.sort()
arr=[0]*(10**6+1)
flag=[True]*(10**6+1)
ans=0
for i in range(n):
    if flag[a[i]]:
        arr[a[i]]+=1
        for j in range(a[i]*2,10**6+1,a[i]):
            flag[j]=False
print(arr.count(1))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int, input().split()))
a.sort()
m=max(a)
arr=[0]*(m+1)
flag=[True]*(m+1)
ans=0
for i in range(n):
    if flag[a[i]]:
        arr[a[i]]+=1
        if not arr[a[i]]==1:
            continue
        for j in range(a[i]*2,m+1,a[i]):
            flag[j]=False
print(arr.count(1))
### BUGGY CODE ###

#!python3

import sys
from functools import reduce
from operator import or_

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    N=len(S)
    lo, hi = 100, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = lo
    S1 = [None] * nn

    for i in range(nn):
        i1 = i * nn
        S1[i] = set(S[j] for j in range(i1, min(N, i1+nn)))

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            i1 = i // nn
            S[i] = j
            i2 = i1 * nn
            S1[i1] = set(S[k] for k in range(i2, min(N, i2+nn)))
        elif cmd == "2":
            j = int(j)
            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            if ia < ja:
                ss = set()
                ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

                if ib > 0:
                    for i1 in range(i, i-ib+nn):
                        ss.add(S[i1])
                if jb > 0:
                    for i1 in range(ja*nn, j):
                        ss.add(S[i1])
            else:
                ss = set(S[k] for k in range(i, j))

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys

from bisect import bisect, insort_left

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i)-1)
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

    print(*ans, sep="\n")

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

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    ans = []
    for _ in range(N):
        tmp = inputInt()
        if tmp in ans:
            ans.remove(tmp)
        else:
            ans.append(tmp)
            ans.sort()
        
    print(len(ans))
        
            	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    ans = {}
    for _ in range(N):
        tmp = inputInt()
        if tmp in ans:
            ans[tmp] += 1
        else:
            ans[tmp] = 1
        
    o = 0
    for v in ans.values():
        if v % 2 == 1:
            o += 1
    print(o)
        
            	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

from collections import Counter

mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    a_sub = a[i+1:]
    a_sub_dict = dict(Counter(a_sub))
    for j in a_sub_dict.keys():
        ans += a_sub_dict[j] * (a[i] ^ j)
print(ans % mod)


### FIXED CODE ###

n = int(input())
a = map(int, input().split())
mod = 10**9 + 7
p=[0] * 60
for a_ in a:
  for i in range(60):
    p[i] += (a_ >> i) & 1
ans = 0
for i in range(60):
  sn = (n - p[i]) * p[i]
  ans = (ans + (sn << i)) % mod
print(ans)
### BUGGY CODE ###

from operator import itemgetter, attrgetter
#input
n = int(input())
H = [list(map(int, input().split())) for _ in range(n)]
C = sorted(H, key = itemgetter(0, 1), reverse = True)
A = sorted(H, key = itemgetter(1, 0), reverse = True)

ans_c = 0
ans_a = 0
turn = 0

while C != [] and A != []:
    if turn % 2 == 0: #chokudai 
        if C[0][0] - A[0][0] >= A[0][1] - C[0][1]:
            chokudai = C.pop(0)
            ans_c += chokudai[0]
            A = sorted(C, key = itemgetter(1, 0), reverse = True)
        else:
            chokudai = A.pop(0)
            ans_c += chokudai[0]
            C = sorted(A, key = itemgetter(0, 1), reverse = True)
    else: #aoki
        if A[0][1] - C[0][1] >= C[0][0] - A[0][0]:
            aoki = A.pop(0)
            ans_a += aoki[1]
            C = sorted(A, key = itemgetter(0, 1), reverse = True)
        else:
            aoki = C.pop(0)
            ans_a = aoki[1]
            A = sorted(C, key = itemgetter(1, 0), reverse = True)
    turn += 1

print(ans_c - ans_a)


### FIXED CODE ###

#input
n = int(input())
H = []
for _ in range(n):
    a, b = map(int, input().split())
    H.append([a + b, a, b])

H = sorted(H, reverse = True)
sum_c = 0
sum_a = 0

for i in range(n):
    if i % 2 == 0:
        sum_c += H[i][1]
    else:
        sum_a += H[i][2]

ans = sum_c - sum_a
print(ans)
### BUGGY CODE ###

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

L = [N]
c = 2
while c < N**0.5:
    if L[-1] != N//c:
        L.append(N//c)
    c += 1
if c > N**0.5:
    c -= 1
    L.append(c)
else:
    L.append(c)


L.reverse()
dp = [[0 for j in range(c+len(L))] for i in range(K+1)]

for j in range(1, c+1):
    dp[2][j] = N//j
for j in range(1, len(L)):
    dp[2][j+c] = N//L[j]*(L[j]-L[j-1])

for i in range(2, K):
    dp[i+1][1] = sum(dp[i])
    for j in range(2, c+len(L)):
        dp[i+1][j] = dp[i+1][j-1]-dp[i][len(dp[0])+1-j]
    for j in range(1, len(L)):
        dp[i+1][j+c] *= (L[j]-L[j-1])
        

print(sum(dp[K])%(10**9+7))

### FIXED CODE ###

from itertools import accumulate

N,K = map(int, input().split())
mod = 10**9+7
sqt = int(N**0.5)
cnt = [N // i-N // (i+1) for i in range(1, N//sqt)] + [1]*sqt
x = cnt
for _ in range(K):
    x = [(i*j)%mod for i, j in zip(accumulate(reversed(x)), cnt)]
    

print(x[-1])
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC141 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
S = input()
dp = [[0 for _ in range(n+1)] for _ in range(math.ceil(n/2)+1)]
for k in range(1,math.ceil(n/2)+1):
    s,t = S[:k],S[k:]
    for i in range(k):
        for j in range(n-k):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j+1],dp[i+1][j])
print(max(dp[-1]))

### FIXED CODE ###

#!/usr/bin/env python3
#ABC141 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = input()
dp = [[0]*(n+1) for _ in range(n+1)]
dp[-1][-1] = 1
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
    for j in range(n):
        ans = max(ans,min(i-j,dp[i][j]))
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3

import math
import sys


DEBUG = False


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, A):
    allxor = 0
    for a in A:
        allxor ^= a

    B = [0] * N

    ans = 0
    bcount = 0
    for bit in range(61, -1, -1):
        mask = 1 << bit
        if allxor & mask:
            ans <<= 1
            ans |= 1
            continue

        bset = set()
        for i in range(N):
            b = B[i]
            b <<= 1
            b |= (A[i] & mask) >> bit
            B[i] = b
            bset.add(b)
        bcount += 1

        full_bit = (1 << bcount) - 1

        blist = list(bset)
        blist1 = blist[:len(blist) // 2]
        blist2 = blist[len(blist) // 2:]

        r1 = set([0])
        for b in blist1:
            for c in list(r1):
                r1.add(b ^ c)

        r2 = set([0])
        for b in blist2:
            for c in list(r2):
                r2.add(b ^ c)

        best = full_bit - 1
        for b1 in r1:
            if b1 ^ full_bit in r2:
                best = full_bit
                break

        bestb = best & 1
        ans <<= 1
        ans |= bestb

        if bestb == 0:
            for i in range(N):
                B[i] >>= 1
            bcount -= 1

    return ans + (ans ^ allxor)


def main():
    N = int(inp())
    A = [int(e) for e in inp().split()]
    print(solve(N, A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3

import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, A):
    allxor = 0
    for a in A:
        allxor ^= a

    while len(A) < 61:
        A.append(0)
    M = len(A)

    row = 0
    ans = 0
    for bi in range(61, -1, -1):
        b = 1 << bi
        if b & allxor:
            ans |= b
            continue

        if not (A[row] & b):
            j = -1
            for i in range(row + 1, M):
                if A[i] & b:
                    j = i
                    break
            if j == -1:
                continue

            A[row], A[j] = A[j], A[row]

        assert A[row] & b
        if not (ans & b):
            ans ^= A[row]

        for i in range(row + 1, M):
            if A[i] & b:
                A[i] ^= A[row]
            assert not (A[i] & b)

        row += 1

    return ans + (ans ^ allxor)


def main():
    N = int(inp())
    A = [int(e) for e in inp().split()]
    print(solve(N, A))


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

n = int(input())
x = list(map(int, input().split()))
a = map(lambda x: x[(n-1)//2], [sorted(x[:i] + x[i+1:]) for i in range(n)])
for i in a:
  print(i)

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
m1, m2 = sorted(x)[n//2-1], sorted(x)[n//2]
for i in x:
  print(m1) if i >= (m1+m2)/2 else print(m2)
### BUGGY CODE ###

S = str(input())
Q = int(input())

S_normal = S
S_inverse = S[::-1]
for q in range(Q):
    tmp1 = []
    tmp2 = []
    query = list(map(str, input().split()))
    if int(query[0]) == 1:
        S = S_inverse
        S_inverse = S_normal
        S_normal = S
    else:
        if int(query[1]) == 1:
            tmp1.append(query[2])
            tmp1.append(S)
            S = ''.join(tmp1)
            S_normal = S
            tmp2.append(S_inverse)
            tmp2.append(query[2])
            S_inverse = ''.join(tmp2)
        else:
            tmp2.append(S)
            tmp2.append(query[2])
            S = ''.join(tmp2)
            S_normal = S
            tmp1.append(query[2])
            tmp1.append(S_inverse)
            S_inverse = ''.join(tmp1)

print(S)

### FIXED CODE ###

from collections import deque

S = str(input())
Q = int(input())

d = deque(list(S))

rev = False

for q in range(Q):
    query = list(map(str, input().split()))
    if int(query[0]) == 1:
        if rev:
            rev = False
        else:
            rev = True
    else:
        if int(query[1]) == 1:
            if not rev:
                d.appendleft(query[2])
            else:
                d.append(query[2])
        else:
            if not rev:
                d.append(query[2])
            else:
                d.appendleft(query[2])

if rev:
    print(''.join(d)[::-1])
else:
    print(''.join(d))
### BUGGY CODE ###

from collections import Counter
from itertools import chain


def prime_set(N):
    """
    Nまでの素数のsetを返す
    """
    if N < 4:
        return ({}, {}, {2}, {2, 3})[N]
    Nsq = int(N ** 0.5 + 0.5) + 1
    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
    for i in range(5, Nsq, 2):
        if i in primes:
            primes -= set(range(i * i, N + 1, i * 2))
    return primes


N = int(input())
A = list(map(int, input().split()))
prime = prime_set(10 ** 6 + 1)


C = Counter(A)
if C[1] == 1:
    print(1)
    exit()
if C[1] >= 2:
    print(0)
    exit()

ans = 0
for a, v in C.items():
    if v >= 2:
        ans += v
        continue
    if a in prime:
        continue
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            if C[i] > 0:
                ans += 1
                break
            if C[a // i] > 0:
                ans += 1
                break

print(N-ans)

### FIXED CODE ###

from collections import Counter
U = 10 ** 6 + 1

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

C = Counter(A)
dp = [0] * U

ans = 0
for k in sorted(C.keys()):
    if dp[k]:
        continue
    if C[k] == 1:
        ans += 1
    for i in range(k, U, k):
        dp[i] = 1

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

n,k =map(int,input().split())
x = list(map(int, input().split()))
a = [0] * n
a[1] = abs(x[0]-x[1])
for i in range (2,n):
    a[i] = min([abs(x[i]-x[j])+a[j] for j in range(max(0,i-k),i)])
print (a[-1])

### FIXED CODE ###

def main():
    
    n,k =map(int,input().split())
    x = list(map(int, input().split()))
    a = [0]*n
    for i in range (1,n):
        a[i]=(min([abs(x[i]-x[j])+a[j] for j in range(max(0,i-k),i)]))
    print (a[-1])
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n= int(input())
a = list(int(i) for i in input().split())
a2 = list(set(a))
ans = 0
for i in a2:
  if a.count(i) <i:
   ans += a.count(i)
  else:
   ans += (a.count(i)-i)
print(ans)

### FIXED CODE ###

import collections
n= int(input())
a = list(int(i) for i in input().split())
c = collections.Counter(a)
a2 = list(set(a))
ans = 0
for i in a2:
  tmp = c[i]
  if tmp <i:
   ans += tmp
  else:
   ans += (tmp-i)
print(ans)