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

from collections import deque

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())
maze = [input() for _ in range(h)]

INF = 10**12
path = [[INF] * w for _ in range(h)] #ここに各マスの移動コストを記録する

walk = [(1,0), (0,1), (-1,0), (0,-1)] #ワープしない移動
warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)] + walk] #ワープするときの移動

q = deque()
path[ch][cw] = 0
q.append((ch, cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and path[nx][ny] > s:
            path[nx][ny] = s
            q.append((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and path[nx][ny] > s+1:
            path[nx][ny] = s+1
            q.append((nx, ny, s+1))

ans = path[dh][dw] if path[dh][dw] < INF else -1
print(ans)

### FIXED CODE ###

from collections import deque


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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

def main():
    n=int(input())
    T=sorted(set(list(int(input()) for _ in  range(n))))[::-1]
    k=T[0]
    while 1:
        for t in T:
            if k%t>0:
                k += T[0]
                break
        else: #for文がbreakしなければここを読む.
            print(k)
            break
main()

### FIXED CODE ###

from fractions import gcd
#from math import gcd
def lcm(a,b):
    return a*b//gcd(a,b)
def main():
    n=int(input())
    T=set(list(int(input()) for _ in  range(n)))
    ans=1
    for t in T:
        ans = lcm(t,ans)
    print(ans)
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)

a=open(0)
N,_,*a = map(int, a.read().split())

dp = [-1 for _ in range(150000)]
dp[0] = 0
def rec(i):
    if dp[i] >= 0:
        return dp[i]
    if i in a:
        dp[i] = 0
        return 0
    if i<3:
        dp[i] = rec(i-1) + 1
        return dp[i]
    dp[i] = (rec(i-1)+rec(i-2))%1000000007
    return dp[i]
    
print(rec(N))




### FIXED CODE ###

import sys

sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 1000000007

a=open(0)
N,_,*a = map(int, a.read().split())

dp = [-1 for _ in range(100010)]
dp[0] = 0
for i in a: dp[i] = 0
def rec(i):
    if dp[i] > -1:
        return dp[i]
    if i<3:
        dp[i] = rec(i-1) + 1
        return dp[i]
    dp[i] = (rec(i-1)+rec(i-2))%MOD
    return dp[i]
    
print(rec(N))
### BUGGY CODE ###

from fractions import gcd
 
N=int(input())
a_list = tuple(int(i) for i in input().split())
MOD = 10**9+7

def cal_lcm(a, b):
  return int(a*b//gcd(a,b))

lcm = 1
for i in range(N):
  lcm = cal_lcm(lcm, a_list[i])
  
ans = 0
for i in range(N):
  ans += (lcm//a_list[i])%MOD

print(ans%MOD)

### FIXED CODE ###

from fractions import gcd
 
N=int(input())
a_list = tuple(int(i) for i in input().split())
MOD = 10**9+7

def cal_lcm(a, b):
  return int(a*b//gcd(a,b))

lcm = 1
for i in range(N):
  lcm = cal_lcm(lcm, a_list[i])
  
ans = 0
for i in range(N):
  ans += lcm//a_list[i]
print(ans%MOD)
### BUGGY CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output


def chkprint(*args):
    names = {id(v): k for k, v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg), '???')+' = '+repr(arg) for arg in args))

# Binary converter


def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]

# --------------------------------------------


dp = None


def main():
    N = int(input())
    X = li_input()

    sX = sorted(X)

    for x in X:
        if sX.index(x) < len(sX) // 2:
            print(sX[len(sX) // 2])
        else:
            print(sX[len(sX) // 2 - 1])


main()


### FIXED CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output


def chkprint(*args):
    names = {id(v): k for k, v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg), '???')+' = '+repr(arg) for arg in args))

# Binary converter


def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]

# --------------------------------------------


dp = None


def main():
    N = int(input())
    X = li_input()

    sX = sorted(X)
    med = sX[len(sX) // 2]
    med_min = sX[len(sX) // 2 - 1]

    for x in X:
        if x < med:
            print(med)
        else:
            print(med_min)


main()
### BUGGY CODE ###

n=int(input())
c=[[] for i in range(n+1)]
d=[[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n-1):
    x,y,z=map(int,input().split())
    c[x].append(y)
    c[y].append(x)
    d[x][y]=z%2
    d[y][x]=z%2
stack=[1]
color=[-1]*(n+1)
color[1]=0
parent=[None]*(n+1)
append=stack.append
while stack:
    i=stack.pop()
    for j in c[i]:
        if j==parent[i]:
            continue
        color[j]=(color[i]+d[i][j])%2
        parent[j]=i
        append(j)
print("\n".join(map(str,color[1:])))

### FIXED CODE ###

n=int(input())
c=[[] for i in range(n+1)]
d={}
for i in range(n-1):
    x,y,z=map(int,input().split())
    c[x].append(y)
    c[y].append(x)
    d[x,y]=z
d[1,1]=0
stack=[1]
parent=[None]*(n+1)
while stack:
    i=stack.pop()
    for j in c[i]:
        if j==parent[i]:
            continue
        parent[j]=i
        d[1,j]=d[1,i]+d[tuple(sorted([i,j]))]
        stack.append(j)
for i in range(1,n+1):
    print(d[1,i]%2)
### BUGGY CODE ###

n=int(input())
l=[]
for _ in range(n):
  s=input()
  s=''.join(sorted(s))
  l.append(s)
c=0
for i in range(n):
  for j in range(i+1,n):
    if l[i]==l[j]:
      c=c+1
print(c)
  
  
  

### FIXED CODE ###

from itertools import groupby
n=int(input())
l=[]
for _ in range(n):
  s=input()
  s=''.join(sorted(s))
  l.append(s)
l.sort()
c=0
for i,j in groupby(l):
  z=len(list(j))
  c=c+(z*(z-1)//2)
print(c)
### BUGGY CODE ###

def main():
    N, K = map(int,input().split())
    h = [int(v) for v in input().split()]
    
    dp = [0 for _ in range(N)]
    dp[1] = abs(h[0] - h[1])
    
    for i in range(2, N):
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(i - K, i) if j >= 0])
    
    print(dp[-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, K = map(int,input().split())
    h = list(map(int,input().split()))
    
    dp = [0] * N
    dp[1] = abs(h[0] - h[1])
    
    for i in range(2, N):
        dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i - K), i))
    
    print(dp[-1])

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

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

dp=[[[0]*2 for i in range(n+1)] for ii in range(n+1)]

dp[0][0][0]=0
dp[0][0][1]=0
dp[1][0][0]=0
dp[1][0][1]=1
dp[1][1][0]=1
dp[1][1][1]=1

mod=10**9+7
for nn in range(2,n+1):
    dp[nn][0][0]=0
    dp[nn][0][1]=nn
    for kk in range(1,nn):
        dp[nn][kk][0]=dp[nn-1][kk][0]
        dp[nn][kk][1]=(dp[nn-1][kk-1][1]+nn)%mod
    dp[nn][nn][0]=(dp[nn-1][nn-1][0]+nn)%mod
    dp[nn][nn][1]=(dp[nn-1][nn-1][1]+nn)%mod
ksum=0
for kk in range(k-1,n+1):
    ksum=ksum+(dp[n][kk][1]-dp[n][kk][0]+1)%mod
print(ksum)

### FIXED CODE ###

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

dp=[[0]*2 for i in range(n+1)] 
mod=10**9+7

dp[0][0]=0
dp[0][1]=n
for i in range(n):
    dp[i+1][0]=(dp[i][0]+(i+1))%mod
dp[n][1]=dp[n][0]
for i in range(n-1,0,-1):
    dp[i][1]=(dp[i+1][1]-(n-1-i))%mod

mod=10**9+7

ksum=0
for kk in range(k-1,n+1):
    ksum=(ksum+dp[kk][1]-dp[kk][0]+1)%mod
print(ksum)
### BUGGY CODE ###

a = int(input())
b = 1
c = []
for i in range(a):
    c.append(b)
    b += 1

D = 0
for I in range(a):
    if c[I]%15 == 0:
        c.remove(c[I])
        c.insert(I,'a')

    elif c[I]%5 == 0:
        c.remove(c[I])
        c.insert(I,'a')
    
    elif c[I]%3 == 0:
        c.remove(c[I])
        c.insert(I,'a')
        
    else:
        D = D + c[I]
print(D)

### FIXED CODE ###

a = int(input())
d = 1
D = 0
for I in range(a):
    if d%3 == 0:
        d += 1
    
    elif d%5 == 0:
        d += 1
        
    else:
        D = D + d
        d += 1
print(D)
### BUGGY CODE ###

s = input()
c = 0
for i in range(len(s)):
    for j in range(i+4,len(s)+1):
        a = int(s[i:j])
        if a>2019:
            if a%2019==0:
                c+=1
print(c)

### FIXED CODE ###

s = input()
len_s = len(s)
pre = 0
mod = [0]*2019
mod[0]=1
x = 1
for i in range(len_s):
    pre = (x*int(s[len_s-i-1])+pre)%2019
    mod[pre] += 1
    x *= 10
    x %= 2019
print(sum([m*(m-1)//2 for m in mod]))
### BUGGY CODE ###

s = input()
q = int(input())

t = 0
for i in range(q):
    query = input()
    if query == '1':
        if t == 1:
            t = 0
        else:
            t = 1
    else:
        if query[2] == '1':
            if t == 0:
                s = query[4:]+s
            else:
                s = s+query[4:][::-1]
        else:
            if t == 0:
                s = s+query[4:]
            else:
                s = query[4:][::-1] + s

if t == 1:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

s = input()
q = int(input())

t = 0
l = ''
r = ''
for i in range(q):
    query = input()
    if query == '1':
        if t == 1:
            t = 0
        else:
            t = 1
    else:
        if query[2] == '1':
            if t == 0:
                l = query[4:]+l
            else:
                r = r+query[4]
        else:
            if t == 0:
                r = r+query[4]
            else:
                l = query[4] + l
s = l+s+r
if t == 1:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(str(input()))
agct = {'A', 'C', 'G', 'T'}

for _ in range(Q):
    l, r = map(int, input().split())

    ans = 0
    fa = 0
    for i in range(l-1, r):
        if S[i] == 'A' and fa == 0:
            fa = 1
        elif S[i] == 'C' and fa == 1:
            fa = 0
            ans += 1
        else:
            fa = 0
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = list(str(input()))

ans_list = []
fa = 0
ans = 0
for index, s in enumerate(S):
    if s == 'A' and fa == 0:
        fa = 1
        ans_list.append(ans)
    elif s == 'A' and fa == 1:
        ans_list.append(ans)
    elif s == 'C' and fa == 1:
        fa = 0
        ans += 1
        ans_list.append(ans)
    else:
        fa = 0
        ans_list.append(ans)
for _ in range(Q):
    l, r = map(int, input().split())
    print(ans_list[r-1] - ans_list[l-1])
### BUGGY CODE ###

def bisect_left(array, i):
    n = len(array)
    mid = n // 2
    if n == 1:
        if array[0] < i:
            return 1
        else:
            return 0
    if i <= array[mid]:
        return bisect_left(array[:mid],i)
    else:
        return mid + bisect_left(array[mid:],i)

def bisect_right(array, i):
    n = len(array)
    mid = n // 2
    if n == 1:
        if i < array[0] :
            return 0
        else:
            return 1
    if array[mid] <= i:
        return  mid + bisect_right(array[mid:],i)
    else:
        return bisect_right(array[0:mid],i)

N = int(input())
L = []
for _ in range(3):
    l = list(map(int,input().split()))
    L.append(sorted(l))
ans = 0
for x in L[1]:
    n = bisect_left(L[0],x)
    m = bisect_right(L[2],x)
    m = N - m
    ans += n*m
print(ans)

### FIXED CODE ###

N = int(input())
L = []
for _ in range(3):
    l = list(map(int,input().split()))
    L.append(sorted(l))
import bisect
ans = 0
for x in L[1]:
    n = bisect.bisect_left(L[0],x)
    m = bisect.bisect_right(L[2],x)
    m = N - m
    ans += n*m
print(ans)
### BUGGY CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
#重さ、価値の順
dp=[[0]*(w+1) for i in range(n+1)]
#配列のインデックスを重さに対応させる

for i in range(n):
    for sum_w in range(w+1):
        
        if sum_w-l[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])
        #l[i]を入れるとき
        dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])
        #入れない時
print(dp[-1][-1])

### FIXED CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
#[w,v]
#重さに対応するインデックスに価値を保存する
dp=[[0]*(w+1) for i in range(n+1)]
 
for i in range(n):
    for sum_w in range(1,w+1):
        if sum_w-l[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])
        #i番目の品を入れる場合
    
        dp[i+1][sum_w]=max(dp[i][sum_w],dp[i+1][sum_w])
        #i番目の品を入れない場合
print(dp[-1][-1])
### BUGGY CODE ###

from heapq import heapify,heappop,heappush
import sys
read=sys.stdin.readline
class mset:
    def __init__(self):
        self.p,self.q,self.dic=[],[],{}
        heapify(self.p);heapify(self.q)
    def add(self,a):
        heappush(self.p,a)
        if not a in self.dic:
            self.dic[a]=1
        else:
            self.dic[a]+=1
    def delete(self,a):
        if a in self.dic and self.dic[a]>0:
            heappush(self.q,a)
            self.dic[a]-=1
    def search(self,a):
        return a in self.dic
    def minimum(self):
        while self.q and self.p[0]==self.q[0]:
            heappop(self.p);heappop(self.q)
        return self.p[0] if self.p else None

N,Q=map(int,read().split())
event=[]
for i in range(N):
    S,T,X=map(int,read().split())
    event.append((1,S-X,X))
    event.append((0,T-X,X))

s=mset()
now=0
for i in range(Q):
    D=int(input())
    event.append((2,D,0))
event.sort(key=lambda x:(x[1],x[0]))

for c,t,w in event:
    if c==0:
        s.delete(w)
    elif c==1:
        s.add(w)
    else:
        m=s.minimum()
        print(-1 if m==None else m)

### FIXED CODE ###

from heapq import heapify,heappop,heappush
import sys
read=sys.stdin.readline
class mset:
    def __init__(self):
        self.p,self.q=[],[]
        heapify(self.p);heapify(self.q)
    def add(self,a):
        heappush(self.p,a)
    def delete(self,a):
            heappush(self.q,a)
    def minimum(self):
        while self.q and self.p[0]==self.q[0]:
            heappop(self.p);heappop(self.q)
        return self.p[0] if self.p else None

N,Q=map(int,read().split())
event=[]
for i in range(N):
    S,T,X=map(int,read().split())
    event.append((1,S-X,X))
    event.append((0,T-X,X))

s=mset()
now=0
for i in range(Q):
    D=int(read())
    event.append((2,D,0))
event.sort(key=lambda x:(x[1],x[0]))

for c,t,w in event:
    if c==0:
        s.delete(w)
    elif c==1:
        s.add(w)
    else:
        m=s.minimum()
        print(-1 if m==None else m)
### BUGGY CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(int,input().split()))
numbers=[]
for _ in range(M):
    B,C=map(int,input().split())
    number=[C]*B
    numbers+=number
    numbers=sorted(numbers,reverse=True)
    numbers=numbers[:N]
numbers+=A
answer=sorted(numbers,reverse=True)
print(sum(answer[:N]))


### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(int,input().split()))
heapq.heapify(A)
numbers=[]
for _ in range(M):
    B,C=map(int,input().split())
    numbers.append([C,B])
numbers=sorted(numbers,reverse=True)
for number in numbers:
    B=number[1]
    C=number[0]
    for _ in range(B):
        a = heapq.heappop(A)
        if C <= a:
            heapq.heappush(A, a)
            break
        else:
            heapq.heappush(A,C)
print(sum(A))
### BUGGY CODE ###

N, K = map(int, input().split())
list_H = [int(x) for x in input().split()]

list_H.sort()

while K :
    if list_H :
        list_H.pop()
    K -= 1

sum = 0
while list_H :
    sum += list_H[0]
    list_H.pop(0)

print(sum)


### FIXED CODE ###

N, K = map(int, input().split())
list_H = [int(x) for x in input().split()]

list_H.sort()

while K :
    if list_H :
        list_H.pop()
    K -= 1

print(sum(list_H))
### BUGGY CODE ###

mod = 1000000007
L = input()
ans1 = 1
ans2 = 0
for i in range(len(L)):
    if L[i] == "0":
        continue
    ans2 += ans1 * 3 ** (len(L) - i - 1) % mod
    ans2 %= mod
    ans1 *= 2
    ans1 %= mod
print((ans1 + ans2) % mod)


### FIXED CODE ###

mod = 1000000007

L = input()

threes = [1] * (len(L) + 1)
for i in range(1, len(L) + 1):
    threes[i] = threes[i-1] * 3 % mod

ans1 = 1
ans2 = 0
for i in range(len(L)):
    if L[i] == "0":
        continue
    ans2 += ans1 * threes[len(L) - i - 1] % mod
    ans2 %= mod
    ans1 *= 2
    ans1 %= mod
print((ans1 + ans2) % mod)
### BUGGY CODE ###

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

minv = 0
maxv = 1000000000

nxt = [0] * (n + 1)
while minv != maxv:
  nxt[0] = (minv + maxv) // 2
  for i in range(n):
    nxt[i+1] = a[i] * 2 - nxt[i]
#  print(nxt)
  if nxt[0] == nxt[n]:
    break
  elif nxt[0] > nxt[n]:
    maxv = nxt[0]
  else:
    minv = nxt[0]
    
for i in range(n):
  print(nxt[i], end=' ')

### FIXED CODE ###

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

minv = 0
maxv = 1000000000

nxt = [0] * (n + 1)
for i in range(n):
  nxt[i+1] = a[i] * 2 - nxt[i]

ans = [0] * (n + 1)
ans[0] = nxt[n] // 2

for i in range(n):
  ans[i+1] = a[i] * 2 - ans[i]
    
for i in range(n):
  print(ans[i], end=' ')
### BUGGY CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10000000)

N, M, P = map(int, input().split())
# ABC = [list(map(int, input().split())) for _ in range(M)]
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

# print (ABC_d)

cost = np.empty(N, dtype = int) - np.inf
cost[0] = 0

def solve(pos, already):
    global cost
    global already2

    if not(pos in ABC_d): return
    # print (already)

    for B, C in ABC_d[pos]:
        if already[B - 1] == True:
            if cost[B - 1] == np.inf:
                pass
            elif cost[B - 1] < cost[pos - 1] + C:
                cost[B - 1] = np.inf
                solve(B, already)
        else:
            if cost[B - 1] < cost[pos - 1] + C:
                cost[B - 1] = cost[pos - 1] + C
                already2 = already.copy()
                already2[B - 1] = True
                solve(B, already2)


already = np.zeros(N, dtype = bool)
already[0] = True
solve(1, already)

if (cost[-1] == np.inf):
    print (-1)
else:
    print (max(0, int(cost[-1])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

f_inf = sys.maxsize

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
cost[0] = 0

def solve(pos, cnt):
    global cost

    if not(pos in ABC_d): return
    if cnt > N: cost[pos-1] = f_inf;

    for B, C in ABC_d[pos]:
        if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
            pass
        elif cost[pos-1] == f_inf:
            cost[B-1] = f_inf
            solve(B, cnt + 1)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            solve(B, cnt + 1)

solve(1, 1)

if (cost[-1] == sys.maxsize):
    print (-1)
else:
    print (max(0, int(cost[-1])))
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
s = set()
ans = 0
for i in sorted(set(a)):
    j=i*2
    while j<=1000000:
        s.add(j)
        j+=i
    if i not in s and c[i]==1:
        ans+=1
            
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
s = set()
ans = 0
for i in sorted(set(a)):
    j=i*2
    while j<=1000000:
        s.add(j)
        j+=i
    if i not in s and c[i]==1:
        ans+=1
            
print(ans)
### BUGGY CODE ###

# coding: utf-8
N = int(input())
S = 'D' + input()

rgb_count = [[0 for i in range(3)] for j in range(N+1)]
for i in range(1, N+1):
    if S[i] == 'R':
        rgb_count[1][0] += 1
    elif S[i] == 'G':
        rgb_count[1][1] += 1
    else:
        rgb_count[1][2] += 1

for i in range(1, N):
    if S[i] == 'R':
        rgb_count[i+1][0] = rgb_count[i][0] - 1
        rgb_count[i + 1][1] = rgb_count[i][1]
        rgb_count[i + 1][2] = rgb_count[i][2]
    elif S[i] == 'G':
        rgb_count[i + 1][0] = rgb_count[i][0]
        rgb_count[i+1][1] = rgb_count[i][1] - 1
        rgb_count[i + 1][2] = rgb_count[i][2]
    else:
        rgb_count[i + 1][0] = rgb_count[i][0]
        rgb_count[i + 1][1] = rgb_count[i][1]
        rgb_count[i+1][2] = rgb_count[i][2] - 1


dict={'R':0, 'G':1, 'B':2}
d = ['', 'B', 'G', 'R']
dic = {'R': [1,2], 'G': [0,2], 'B': [0,1]}
ret = 0
for i in range(2,N):
    search = dic[S[i]]
    ret += (rgb_count[1][search[0]] - rgb_count[i][search[0]]) * rgb_count[i+1][search[1]]
    ret += (rgb_count[1][search[1]] - rgb_count[i][search[1]]) * rgb_count[i+1][search[0]]
    ran = min([i-1, N-i])

    if ran < 1: continue
    for k in range(1, ran+1):
        if set([S[i-k], S[i], S[i+k]]) == set(['G', 'B', 'R']):
            ret -= 1

print(ret)

### FIXED CODE ###

# coding: utf-8
N = int(input())
S = 'D' + input()


rgb_count = [[0 for i in range(3)] for j in range(N+1)]
for i in range(1, N+1):
    if S[i] == 'R':
        rgb_count[1][0] += 1
    elif S[i] == 'G':
        rgb_count[1][1] += 1
    else:
        rgb_count[1][2] += 1


dict={'R':1, 'G':2, 'B':4}
d = ['', 'B', 'G', 'R']
dic = {'R': [1,2], 'G': [0,2], 'B': [0,1]}
ret = rgb_count[1][0]*rgb_count[1][1]*rgb_count[1][2]
for i in range(2,N):
    ran = min([i-1, N-i])
    if ran < 1: continue
    for k in range(1, ran+1):
        if dict[S[i-k]]+dict[S[i]]+dict[S[i+k]] == 7:
            ret -= 1

print(ret)
### BUGGY CODE ###

s = list(input())
n = len(s)
a_count = 0
ans = 0
i = 0
while i < n-2:
    i = min(i,0)
    if s[i:i+3] == ['A','B','C']:
        ans +=  1
        s[i:i+3] = ['B','C','A']
        i -= 2
    i += 1
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
s = list(s.replace('BC','D'))
a_count = 0
ans = 0
i = 0
while i < len(s) - 1 :
    if s[i:i+2] == ['A','D']:
        ans += a_count + 1
        s[i+1] = 'A'
        s[i] = 'D'
    else:
        if s[i] == 'A':
            a_count += 1
        else:
            a_count = 0
    i += 1
print(ans)
### BUGGY CODE ###

import itertools
import numpy as np

N = int(input())
points = np.array(list(map(int, input().split())))
ans = 0
s_points = sorted(points)

for k in range(max(points)+1):
    arc_list = points[points >= k]
    abc_list = points[points < k]
    if len(arc_list) == len(abc_list):
        ans += 1

print(ans)

### FIXED CODE ###

import itertools
import numpy as np

N = int(input())
points = np.array(list(map(int, input().split())))
ans = 0
s_points = sorted(points)

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

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

N = int(input())
c = [i for i in range(1, N)]
print(sum(c))

### FIXED CODE ###

N = int(input())
N -= 1
print((N*(N+1))//2)