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

import sys
import scipy.sparse as sparse
from collections import deque

n = int(input())


color_ls = {i:None for i in range(n)}
_map = sparse.lil_matrix((n, n))
already = set()
for i in range(n-1):
    u, v, w = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    if i == 0:
        root = u
    _map[u,v] = w
    _map[v,u] = w
    already.update({u, v})
color_ls[root] = 0
cur = root
already.clear()
que = deque()
while True:
    candidate = _map[cur].nonzero()[1]
    for cand in candidate:
        if cand in already:
            continue
        already.add(cand)
        que.append(cand)
        if _map[cur,cand] % 2 == 0:
            color_ls[cand] = 0 if color_ls[cur] == 0 else 1
        else:
            color_ls[cand] = 1 if color_ls[cur] == 0 else 0
    if len(que) == 0:
        break
    cur = que.popleft()

for i in range(n):
    print(color_ls[i])

### FIXED CODE ###

import sys
from collections import deque

n = int(input())

color_ls = {i: None for i in range(n)}
dict_map = {i : [] for i in range(n)}
already = set()
for i in range(n - 1):
    u, v, w = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    if i == 0:
        root = u
    dict_map[u].append([v, w])
    dict_map[v].append([u, w])
    already.update({u, v})
color_ls[root] = 0
cur = root
already.clear()
que = deque()
while True:
    candidate = dict_map[cur]
    for cand, w in candidate:
        if cand in already:
            continue
        already.add(cand)
        que.append(cand)
        if w % 2 == 0:
            color_ls[cand] = 0 if color_ls[cur] == 0 else 1
        else:
            color_ls[cand] = 1 if color_ls[cur] == 0 else 0
    if len(que) == 0 or len(already) == n:
        break
    cur = que.popleft()

for i in range(n):
    print(color_ls[i])
### BUGGY CODE ###

#!/env/usr/python3
n, k = input().split()
n = int(n)
k = int(k)

a = []
for i in range(n):
	a.append(int(input()))
	#print(a)

a.sort()
#print(a)


height_distance = []
for i, h in enumerate(a):
	if i <= n-k:
		chosen = a[i:i+k]
		height_distance.append(max(chosen)-min(chosen))
		#print(height_distance)

print(min(height_distance))


### FIXED CODE ###

#!/env/usr/python3
n, k = input().split()
n = int(n)
k = int(k)

a = []
for i in range(n):
	a.append(int(input()))
	#print(a)

a.sort()
#print(a)


height_distance = []
for i, h in enumerate(a):
	if i <= n-k:
		#chosen = a[i:i+k]
		#height_distance.append(max(chosen)-min(chosen))
		height_distance.append(a[i+k-1]-a[i])
		#print(height_distance)

print(min(height_distance))
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
LRlist = []
for i in range(Q):
    LRlist.append(list(map(int,input().split())))
indexlist = []
for i in range(len(S)-1):
    if S[i] == 'A':
        if S[i+1] == 'C':
            indexlist.append(i)
for LR in LRlist:
    L = LR[0]
    R = LR[1]
    answer = 0
    for i in indexlist:
        if L - 1 <= i and i <= R - 2:
            answer += 1
        elif R - 2 < i:
            break
    print(answer)

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
LRlist = []
for i in range(Q):
    LRlist.append(list(map(int,input().split())))
t = [0] * (N + 1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0) #t[i]=i文字目までのACのAの数：累積和
for LR in LRlist:
     L = LR[0]
     R = LR[1]
     print(t[R-1] - t[L-1])
### BUGGY CODE ###

n=int(input())
arr=list(map(int,input().split()))
acum=[0]*(n+1)
acum[1]=arr[0]
cnt=0
for i in range(2,n+1):
  acum[i]=acum[i-1]+arr[i-1]
for i in range(n):
  for j in range(1,n-i+1):
    if acum[i+j]-acum[i]==0:
      cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
acum=[0]*(n+1)
cnt=0
for i in range(1,n+1):
  acum[i]=acum[i-1]+arr[i-1]
acum=sorted(acum)
acum.append(10**10)
tmp=1
for i in range(1,len(acum)):
  if  acum[i]==acum[i-1]:
    tmp+=1
  else:
    cnt+=tmp*(tmp-1)//2
    tmp=1
print(cnt)
### BUGGY CODE ###

from heapq import heappop, heappush

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


A.sort()
F.sort(reverse=True)
l = list(zip(A, F))


class Contest():
    def __init__(self, a, f):
        self.a = a
        self.f = f
    
    def __lt__(self, other):
        return self.a * self.f < other.a * other.f

h = []
for i in l:
    heappush(h, Contest(i[0], -1 * i[1]))


for k in range(K):
    a = heappop(h)
    heappush(h, Contest(a.a - 1, a.f))

ans = heappop(h)
print(-1 * ans.a * ans.f)



### FIXED CODE ###

import numpy as np
from math import ceil

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))

A.sort()
F.sort()

if np.sum(A) <= K:
    print(0)
else:
    st = 0
    ed = 10 ** 12
    md = ceil((st + ed) / 2)
    while True:
        if np.sum(A - np.minimum(A, md // F[::-1])) <= K:
            ed = md
        else:
            st = md
        md = ceil((st + ed) / 2)

        if md == ed:
            break

    print(md)
### BUGGY CODE ###

from collections import deque
inf=float("inf")


def BFS():
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque()
    queue.append([Cx-1,Cy-1,0])
    D[Cx-1][Cy-1]=0

    while len(queue)>0:
        x,y,cnt=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and D[X][Y]>cnt:
                    D[X][Y]=cnt
                    queue.append([X,Y,cnt])

        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if S[X][Y]=="." and D[X][Y]>cnt+1:
                    D[X][Y]=cnt+1
                    queue.append([X,Y,cnt+1])

    return D[Dx-1][Dy-1]


h,w=map(int,input().split())
Cx,Cy=map(int,input().split())
Dx,Dy=map(int,input().split())
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
inf=float("inf")


def BFS():
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque()
    queue.append([Cx-1,Cy-1,0])
    D[Cx-1][Cy-1]=0

    while len(queue)>0:
        x,y,cnt=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and D[X][Y]>cnt:
                    D[X][Y]=cnt
                    queue.appendleft([X,Y,cnt])

        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if S[X][Y]=="." and D[X][Y]>cnt+1:
                    D[X][Y]=cnt+1
                    queue.append([X,Y,cnt+1])

    return D[Dx-1][Dy-1]


h,w=map(int,input().split())
Cx,Cy=map(int,input().split())
Dx,Dy=map(int,input().split())
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)
### BUGGY CODE ###

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

ans = 0

for i in range(1000):
    p100 = i // 100
    ki = i % 100
    p10  = ki // 10
    ki = ki % 10
    p1   = ki // 1
    j = 0
    flag = False
    while j < n:
        if flag:
            break
        if int(s[j]) == p100:
            j += 1
            while j < n:
                if flag:
                    break
                if int(s[j]) == p10:
                    j += 1
                    while j < n:
                        if flag:
                            break
                        if int(s[j]) == p1:
                            ans += 1
                            flag = True
                            break
                        else:
                            j += 1
                else:
                    j += 1
        else:
            j += 1
            
print(ans)

### FIXED CODE ###

n = int(input())
S = input()
ct = 0

for i in range(10):
    if str(i) in S:
        p = S.index(str(i))
        Si = S[p+1 :]
        for j in range(10):
            if str(j) in Si:
                q = Si.index(str(j))
                Sj = Si[q+1 :]
                for k in range(10):
                    if str(k) in Sj:
                        ct += 1
print(ct)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
num = [int(input()) for i in range(N)]
num_set = set(tuple(num))
count = 0
for i in num_set:
    if num.count(i)%2 == 1:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
A = {}
for i in range(N):
    a = input()
    A.setdefault(a, 0)
    A[a] = 1 - A[a]
print(sum(A.values()))
### BUGGY CODE ###

import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from collections import defaultdict
#すべてのkeyが用意されてる defaultdict(int)で初期化
from collections import OrderedDict
#順序を保ったdict
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split())
A=100*(n-m)+1900*m
p=pow(2,m)

@lru_cache(maxsize=10**10)
def per(n):
    if n==1:
        return 1/p
    return (1-sum([per(i) for i in range(1,n)]))*(1/p)

ans=0
for i in range(1,10000):
    ans+= i*A*per(i)
print(round(ans))


### FIXED CODE ###

import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from collections import defaultdict
#すべてのkeyが用意されてる defaultdict(int)で初期化
from collections import OrderedDict
#順序を保ったdict
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split())
A=100*(n-m)+1900*m
p=pow(2,m)

@lru_cache(maxsize=10**10)
def per(n):
    if n==1:
        return 1/p
    return (1-sum([per(i) for i in range(1,n)]))*(1/p)

ans=0
for i in range(1,2000):
    ans+= i*A*per(i)
print(round(ans))
### BUGGY CODE ###

import heapq

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

ans = 0
hq = []
for day in range(1, M+1):
    for job in list(jobs):
        if day == job[0]:
            heapq.heappush(hq, - job[1])
            jobs.remove(job)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)


### FIXED CODE ###

import heapq
from collections import defaultdict

N, M = map(int, input().split())
jobs = defaultdict(list)
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

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

S=input()
ans=0
for i in range(len(S)):
  for j in range(len(S)-i):
    j+=i+1
    tmp=S[i:j]
    tmp=int(tmp)
    if tmp%2019==0:
      ans+=1
print(ans)

### FIXED CODE ###

S=input()
unko=[0]*2019
tmp=0
num=1
for s in S[::-1]:
  s=int(s)
  tmp=(tmp+s*num)%2019
  num=(num*10)%2019
  unko[tmp]+=1
ans=0
ans+=(unko[0]+1)*unko[0]/2
for i in unko[1:]:
  ans+=i*(i-1)/2
print(int(ans))
### BUGGY CODE ###

n=int(input())
c = input()
l =list(c)
L = len(l)//2
ans = 0
k = n-1

for i in range(k):
    for j in range(k,i,-1):
        if l[i]== 'W' and l[j] == 'R':
            l[j] = 'W'
            ans += 1
            k = j-1
            break
print(ans)

### FIXED CODE ###

n=int(input())
c=input()
r=c.count("R")
r_1=c[:r].count("R")
ans=r-r_1
print(ans)
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    l = sorted(tuple(map(int, input().rstrip('\n').split())))
    cnt = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            t = l[i] + l[j]
            for k in range(j+1, n):
                if t > l[k]:
                    cnt += 1
                else:
                    break
    print(cnt)


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    import bisect
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    l = list(map(int, input().rstrip('\n').split()))
    l.sort()
    cnt = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            t = l[i] + l[j]
            p = bisect.bisect_left(l, t)
            cnt += (p - j - 1)
    print(cnt)


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

N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for _ in range(N+1)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True


def dfs(cur, last3):
    '''
    if last3 in memo[cur]:
        return memo[cur][last3]
    '''
    if cur == N:
        return 1
    ret = 0
    for x in 'ATGC':
        if ok(last3 + x):
            ret = (ret + dfs(cur + 1, last3[1:] + x)) % MOD
    #memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))


### FIXED CODE ###

N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for _ in range(N+1)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True


def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for x in 'ATGC':
        if ok(last3 + x):
            ret = (ret + dfs(cur + 1, last3[1:] + x)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))
### BUGGY CODE ###

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

now_reverse = False
l = [s]
tmp = ''

for _ in range(n):
  query = input()

  if query == '1':
    now_reverse = not now_reverse
    l.append(-1)
    tmp = 0
    continue

  
  _,f,c = query.split()
  if f == '1' and now_reverse:
    s = "{}{}".format(s,c)
  elif f == '1' and not now_reverse:
    s = "{}{}".format(c,s)
  elif f == '2' and now_reverse:
    s = "{}{}".format(c,s)
  else:
    s = "{}{}".format(s,c)
  
if now_reverse:
  s = reversed(s)

for c in s:
  print(c,end='')
print()

### FIXED CODE ###

from collections import deque
s = input()
n = int(input())
d = deque(s)

now_reverse = False

for _ in range(n):
  query = input()

  if query == '1':
    now_reverse = not now_reverse
    continue

  
  _,f,c = query.split()
  if f == '1' and now_reverse:
    d.append(c)
  elif f == '1' and not now_reverse:
    d.appendleft(c)
  elif f == '2' and now_reverse:
    d.appendleft(c)
  else:
    d.append(c)
  
if now_reverse:
  d = reversed(list(d))
else:
  d =list(d)

for c in d:
  print(c,end='')
print()
### BUGGY CODE ###

import sys

s = input()
n = len(s)
l = [0] * n

for i in range(n):
	state = i
	count = 0
	while True:
		if s[state] == 'R' and s[state+1] == 'L':
			if count % 2 == 0:
				l[state] += 1
			else:
				l[state+1] += 1
			break
		elif s[state] == 'L' and s[state-1] == 'R':
			if count % 2 == 0:
				l[state] += 1
			else:
				l[state-1] += 1
			break
		elif s[state] == 'R' and s[state+1] == 'R':
			state += 1
			count += 1
		elif s[state] == 'L' and s[state-1] == 'L':
			state -= 1
			count += 1
		else:
			print('error')
			break

for i in range(n):
	sys.stdout.write(str(l[i]))
	if i != n-1:
		sys.stdout.write(" ")

### FIXED CODE ###

import sys

s = input()
n = len(s)
l = [0] * n
reverse_s = ''.join(list(reversed(s)))

for i in range(n):
	state = i
	count = 0
	while True:
		if s[state] == 'R' and s[state+1] == 'L':
			if count % 2 == 0:
				l[state] += 1
			else:
				l[state+1] += 1
			break
		elif s[state] == 'L' and s[state-1] == 'R':
			if count % 2 == 0:
				l[state] += 1
			else:
				l[state-1] += 1
			break
		elif s[state] == 'R' and s[state+1] == 'R':
			tmp = s.find('L',state,n) - state
			state += tmp
			count += tmp
		elif s[state] == 'L' and s[state-1] == 'L':
			tmp = reverse_s.find('R',n-state,n) - (n - state)
			state -= tmp
			count += tmp
		else:
			print('error')
			break

for i in range(n):
	sys.stdout.write(str(l[i]))
	if i != n-1:
		sys.stdout.write(" ")
### BUGGY CODE ###

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

for i in range(N):
    temp = []
    for j in range(len(A)):
        if j == i:
            continue
        temp.append(A[j])
        ans = 0
        pos = 0
    for j in temp:
        ans += abs(j-pos)
        pos = j
    ans += abs(temp[-1])
    print(ans)

### FIXED CODE ###

N = int(input())
A = [0]

Astr = input().split()

for i in Astr:
    A.append(int(i))

A.append(0)

ans = 0
pos = 0
for i in range(len(A)):
    if i == 0:
        continue
    ans += abs(A[i]-pos)
    pos = A[i]

for i in range(len(A)):
    if i == 0 or i == len(A)-1:
        continue
    print(ans-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))
### BUGGY CODE ###

n, m = map(int, input().split())
cards = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

c = []
for i in bc:
    for j in range(i[0]):
        c.append(i[1])
        
c.sort(reverse = True)

for i in c:
    cards.sort()
    if cards[0] < i:
        cards[0] = i
    else:
        break
    
print(sum(cards))

### FIXED CODE ###

n, m = map(int, input().split())
cards = [[1, int(i)] for i in input().split()]
bc = [list(map(int, input().split())) for _ in range(m)]
cards += bc
cards.sort(key = lambda x: x[1], reverse = True)

l = []
flag = 0
for i in cards:
    for j in range(i[0]):
        l.append(i[1])
        if len(l) == n:
            flag = 1
            break
    if flag:
        break

print(sum(l))
### BUGGY CODE ###

n=int(input())
s=input()
cnt=[]
for i in range(1,n):
    w=s[:i-1]
    e=s[i:]
    wc=w.count('W')
    ec=e.count('E')
    cnt.append(wc+ec)

print(min(cnt))

### FIXED CODE ###

def we(s):
    cnt=s.count('E')
    ans=s.count('E')
    for i in s:
        if i =='W':
            cnt+=1
        else:
            cnt-=1
            ans=min(ans,cnt)
    return (min(cnt,ans))
input()
print(we(input()))
### BUGGY CODE ###

N, Y = map(int, input().split())
count = 0
while count == 0:
  for a in range(N+1):
    for b in range(N-a+1):
      for c in range(N-a-b+1):
        if Y == 10000*a+5000*b+1000*c and count == 0:
          print("{} {} {}".format(a, b, c))
          count += 1
        else:
          pass

if count == 0:
  print("-1 -1 -1")

### FIXED CODE ###

N, Y = map(int, input().split())
count = 0
for a in range(N+1):
  for b in range(N-a+1):
    if Y == 10000*a+5000*b+1000*(N-a-b) and count == 0:
      print("{} {} {}".format(a, b, N-a-b))
      count += 1
    else:
      pass

if count == 0:
  print("-1 -1 -1")
### BUGGY CODE ###

mods = [0]*2019
mods[0] = 1
s = input()
u = 1
t = 0
for i in range(1,len(s)+1):
    k = len(s) - i
    t = (t + int(s[k])*u)%2019
    u *= 10 % 2019
    mods[t] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)/2
print(int(cnt))

### FIXED CODE ###

mods = [0]*2019
mods[0] = 1
s = input()
t = 0
u = 1
for i in range(1,len(s)+1):
    t = (t + int(s[-i])*u)%2019
    u = u*10%2019
    mods[t] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)/2
print(int(cnt))
### BUGGY CODE ###

n,c=map(int,input().split())
d=[]
for i in range(c):
  d.append(list(map(int,input().split())))
col=[]
for i in range(n):
  col.append(list(map(int,input().split())))
lc1=[]
lc2=[]
lc3=[]
for i in range(c):
  ccount1=0
  ccount2=0
  ccount3=0
  for j in range(n):
    for k in range(n):
      if (j+k)%3==0:
        ccount1+=d[col[j][k]-1][i]
      elif (j+k)%3==1:
        ccount2+=d[col[j][k]-1][i]
      else:
        ccount3+=d[col[j][k]-1][i]
  lc1.append(ccount1)
  lc2.append(ccount2)
  lc3.append(ccount3)
min=10**10
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i==j or j==k or i==k:
        pass
      else:
        if min>lc1[i]+lc2[j]+lc3[k]:
          min=lc1[i]+lc2[j]+lc3[k]
print(min)

### FIXED CODE ###

n,c=map(int,input().split())
d=[]
for i in range(c):
  d.append(list(map(int,input().split())))
col=[]
for i in range(n):
  col.append(list(map(int,input().split())))
lc1=[]
lc2=[]
lc3=[]
for i in range(c):
  ccount1=0
  ccount2=0
  ccount3=0
  for j in range(n):
    for k in range(n):
      if (j+k)%3==0:
        ccount1+=d[col[j][k]-1][i]
      elif (j+k)%3==1:
        ccount2+=d[col[j][k]-1][i]
      else:
        ccount3+=d[col[j][k]-1][i]
  lc1.append(ccount1)
  lc2.append(ccount2)
  lc3.append(ccount3)
min=10**10
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i==j or j==k or i==k:
        pass
      else:
        if min>lc1[i]+lc2[j]+lc3[k]:
          min=lc1[i]+lc2[j]+lc3[k]
print(min)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
A.sort()
M=10**6+1
cnt=[True]*M
dep=[x for x in set(A) if A.count(x) >= 2]
for i in A:
    if cnt[i]==False:
        continue
    for j in range(2*i,M,i):
        #print(i,M,j)
        cnt[j]=False
ans=0
for i in A:
    if cnt[i] and i not in dep:
        ans+=1
print(ans)


### FIXED CODE ###

from collections import Counter
max_=10**6+1
ans=0

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

b=[True]*(max_+1)
data.sort()
c=Counter(data)
#print(c)

for d in data:
    if b[d]:
        for j in range(d,max_,d):
            b[j]=False
        if c[d]==1:#複数存在考慮
            ans+=1
print(ans)
### BUGGY CODE ###

s,k=input().split();k,o,c,z,L,O=int(k),s.count("1")+1,0,0,[],998244353;M,r=min(o,k+1),range
for i in s:
 if i=="0":L+=[c];c=0
 else:c+=1
d=[[0]*M for _ in r(o)];d[0][0]=1
for i in L:
 D=[[0]*M for _ in r(o)]
 for j in r(o):
  for l in r(max(z+i-j,0),o-j):
   m=max(l-i,0)
   for p in r(min(j+1,M-m)):D[j+l][p+m]=(D[j+l][p+m]+d[j][p])%O
 z+=i;d=D
print(sum([sum(i)for i in d])%O)

### FIXED CODE ###

def main():
    mod = 998244353
    s, k = input().split()
    k = int(k)
    n = len(s)

    one = s.count("1")

    cnt = 0
    zero_list = []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1

    z = 0
    mm = min(one, k)

    dp = [[0]*(one+1) for _ in [0]*(one+1)]
    dp[0][0] = 1

    for i in range(len(zero_list)):
        dp2 = [[0]*(mm+1) for _ in [0]*(one+1)]
        base = zero_list[i]
        # j:何個今までに入れたか
        for j in range(one+1):
            # l:何個入れるか
            for l in range(one+1-j):
                if l < z+base-j:
                    continue
                ml = max(l-base, 0)
                # p:これまでのペナルティ
                for p in range(min(one, k)+1):
                    q = p+ml
                    if q <= mm:
                        dp2[j+l][q] = (dp2[j+l][q]+dp[j][p]) % mod
                    else:
                        break
        z += base
        dp = dp2
    print(sum([sum(i) for i in dp]) % mod)


main()
### BUGGY CODE ###

n = int(input())
ans = 0

for i in range(n):
    ans += i

print(ans)


### FIXED CODE ###

n = int(input())
ans = ((n-1)*n)//2

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

hiki,hon = map(int,input().split())

turu = 0
kame = 0

while(1):
    if hon < 4 or hiki == 0:
        break
    if hon >= 4:
        hon = hon -4
        kame = kame + 1
        hiki = hiki - 1
        
if hon == 2:
    turu = turu + 1
    hiki = hiki -1
    hon = 0
hantei = hon % 2
while(1):
    if hiki == 0 or kame == 0 or hantei == 1:
        break
    else:
        if hiki > 0 and kame > 0 and hantei == 0:
            hiki = hiki - 1
            kame = kame - 1
if hiki == 0 and hon == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

hiki,hon = map(int,input().split())
turu = 0
kame = 0

for i in range(50):
    if hiki > 0 and hon >= 4:
        hon = hon - 4
        kame = kame + 1
        hiki = hiki - 1
    elif hon == 2 and hiki == 1:
        hiki = 0
        hon = 0
    else:
        break

hantei = hon % 2

for i in range(50):
    if hiki == 0 or kame == 0 or hantei == 1:
        break
    elif hiki > 0 and kame > 0 and hantei == 0:
        hiki = hiki - 1
        kame = kame - 1

if hiki == 0 and hon == 0:
    print("Yes")
else:
    print("No")