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

N=int(input())
li=input().split()
Ans=True

for i in range(N):
    for j in range(N):
        if i<=j:
            pass
        else:
            if li[i]==li[j]:
                Ans=False
                break
            else:
                pass

if Ans==True:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

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

for i in range(N-1):
    if A[i]!=A[i+1]:
        ans+=1
    else:
        break

if ans+1==N:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import sys
from collections import Counter
H,W,m = map(int,input().split())
h_ls = [0] * H
w_ls = [0] * W
bombers = [[0,0] for _ in range(m)]
for i in range(m):
    h,w = map(int,input().split())
    h_ls[h-1] += 1
    w_ls[w-1] += 1
    bombers[i] = [h-1,w-1]

h_max = max(h_ls)
h_counter = Counter(h_ls)
# Couter使ってみる
h_max_args = [0]*h_counter[h_max]
next_ind = 0
for i in range(H):
    if h_ls[i] == h_max:
        h_max_args[next_ind] = i
        next_ind += 1

w_max = max(w_ls)
w_counter = Counter(w_ls)
w_max_args = [0]*w_counter[w_max]
next_ind = 0
for i in range(W):
    if w_ls[i] == w_max:
        w_max_args[next_ind] = i
        next_ind += 1

for h in h_max_args:
    for w in w_max_args:
        if not [h,w] in bombers:
            print(w_max+h_max)
            sys.exit()

print(w_max+h_max-1)

### FIXED CODE ###

import sys
from collections import Counter
H,W,m = map(int,input().split())
h_ls = [0] * H
w_ls = [0] * W
bombers = [(0,0) for _ in range(m)]
for i in range(m):
    h,w = map(int,input().split())
    h_ls[h-1] += 1
    w_ls[w-1] += 1
    bombers[i] = (h-1,w-1)

h_max = max(h_ls)
h_counter = Counter(h_ls)
# Couter使ってみる
h_max_args = [0]*h_counter[h_max]
next_ind = 0
for i in range(H):
    if h_ls[i] == h_max:
        h_max_args[next_ind] = i
        next_ind += 1

w_max = max(w_ls)
w_counter = Counter(w_ls)
w_max_args = [0]*w_counter[w_max]
next_ind = 0
for i in range(W):
    if w_ls[i] == w_max:
        w_max_args[next_ind] = i
        next_ind += 1

bombers = set(bombers)
for h in h_max_args:
    for w in w_max_args:
        if not (h,w) in bombers:
            print(w_max+h_max)
            sys.exit()

print(w_max+h_max-1)
### BUGGY CODE ###

#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    i2 = bisect.bisect_right(B, B[N - 1] / 2, lo = 2, hi = N - 1)
    i1 = bisect.bisect_right(B, B[i2 - 1] / 2, lo = 1, hi = i2)
    i3 = bisect.bisect_right(B, B[N - 1] / 2 + B[i2 - 1] / 2, lo = i2 + 1)

    P = B[i1 - 1]
    Q = B[i2 - 1] - B[i1 - 1]
    R = B[i3 - 1] - B[i2 - 1]
    S = B[N - 1] - B[i3 - 1]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = B[N - 1] / 2 - min_d
    max_half = B[N - 1] / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 2, hi = N - 1)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 1)

    for i2 in range(i2_lo, i2_hi + 1):
        i1 = bisect.bisect_right(B, B[i2 - 1] / 2, lo = 1, hi = i2)
        i3 = bisect.bisect_right(B, B[N - 1] / 2 + B[i2 - 1] / 2, lo = i2 + 1)
        i1_lo = i1_hi = i1
        i3_lo = i3_hi = i3
        if B[i1 - 1] * 2 != B[i2 - 1] and i1 + 1 < i2:
            i1_hi += 1
        if B[i3 - 1] * 2 != B[N - 1] + B[i2 - 1] and i3 + 1 < N:
            i3_hi += 1

        for i1 in range(i1_lo, i1_hi + 1):
            for i3 in range(i3_lo, i3_hi + 1):
                P = B[i1 - 1]
                Q = B[i2 - 1] - B[i1 - 1]
                R = B[i3 - 1] - B[i2 - 1]
                S = B[N - 1] - B[i3 - 1]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    T = B[N - 1]

    i2 = bisect.bisect_left(B, T / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = T - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = T / 2 - min_d
    max_half = T / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2) + 1

    for i2 in range(i2_lo, i2_hi):
        if min_d * 2 < abs(T - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)
        i1_lo, i1_hi = i1, i1 + 1
        i3_lo, i3_hi = i3, i3 + 1
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != T + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi):
            P = B[i1]
            Q = B[i2] - B[i1]
            for i3 in range(i3_lo, i3_hi):
                R = B[i3] - B[i2]
                S = T - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


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

from collections import defaultdict


def prepare(n, MOD):
    f = 1
    factorials = [1] * (n + 1)
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials[m] = f
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def prime_factorize(n):
    f = defaultdict(lambda: 0)
    f[2] = len(bin(n & -n)) - 3
    i = 3
    k = n >> f[2]
    while k > 1:
        while True:
            d, m = divmod(k, i)
            if m == 0:
                f[i] += 1
                k = d
            else:
                break
        i += 2
    return f


MOD = 1000000007
n, m = map(int, input().split())
pf = prime_factorize(m)
mx = max(pf.values())
f, r = prepare(n + mx - 1, MOD)
ans = 1
for p, e in pf.items():
    ans *= f[n + e - 1]
    ans %= MOD
    ans *= r[n - 1]
    ans %= MOD
    ans *= r[e]
    ans %= MOD
print(ans)


### FIXED CODE ###

from collections import defaultdict


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def prime_factorize(n):
    f = defaultdict(lambda: 0)
    f[2] = len(bin(n & -n)) - 3
    i = 3
    k = n >> f[2]
    while k > 1:
        while True:
            d, m = divmod(k, i)
            if m == 0:
                f[i] += 1
                k = d
            else:
                break
        i += 2
    return f


MOD = 1000000007
n, m = map(int, input().split())
pf = prime_factorize(m)
mx = max(pf.values())
f, r = prepare(n + mx, MOD)
ans = 1
for p, e in pf.items():
    ans *= f[n + e - 1] * r[n - 1]
    ans %= MOD
    ans *= r[e]
    ans %= MOD
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
b=[0]*n
for i in range(n):
    b[i]=a.index(i+1)+1
maped_b=map(str,b)
ans=' '.join(maped_b)
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
ans=[0]*n
for i in range(n):
    ans[a[i]-1]=str(i+1)
ans=' '.join(ans)
print(ans)
### BUGGY CODE ###

def func(x,y):
    return min(x,y)

class SegmentTree:
    def __init__(self, n): #a1, a2, ..., an
        n_ = 1
        while n_ < n:
            n_ *= 2

        self.n = n_
        self.arr = [10**18] * (2*self.n-1)

    def update(self, k, a): #0_indexed
        k += self.n - 1
        self.arr[k] = a

        while k > 0:
            k = (k-1) // 2
            self.arr[k] = min(self.arr[2*k+1], self.arr[2*k+2])

    def query(self, l, r):
        L, R = l+self.n, r+self.n
        ide_ele = float("inf")
        #単位元(ide_ele)は、区間外の値などに設定する値です。
         #ex) 最小値のセグ木 → +inf
         #　和のセグ木 → 0
         #　積のセグ木 → 1
         #  gcdのセグ木 → 0
        res = ide_ele
        while L < R:
            if R & 1:
                R -= 1
                res = func(res, self.arr[R-1]) #

            if L & 1:
                res = func(res, self.arr[L-1])
                L += 1

            L >>= 1
            R >>= 1

        return res

n,m=map(int,input().split())
lrc=[tuple(map(int,input().split())) for _ in range(m)]
dp=SegmentTree(n+1)
dp.update(1,0)

rl=[[] for _ in range(n+1)]
rc=[[] for _ in range(n+1)]
for l,r,c in lrc:
    rl[r].append(l)
    rc[r].append(c)

for r in range(2,n+1):
    x=float("inf")
    for l,c in zip(rl[r],rc[r]):
        y=dp.query(l,r)+c
        if x>y:
            x=y
    dp.update(r,x)
    if r==n:
        ans=x

if ans==float("inf"):
    ans=-1
print(ans)


### FIXED CODE ###


from collections import defaultdict
from heapq import heappop, heappush


class Graph():

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra():

    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)

            if self.dist[u] < dist_u:
                continue

            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):

        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal

        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]


import sys
input=sys.stdin.readline
n,m=map(int,input().split())
g=Graph()

for _ in range(m):
    l,r,c=map(int,input().split())
    g.add_edge(l,r,c)
for i in range(2,n+1):
    g.add_edge(i,i-1,0)


d = Dijkstra(g,1)
ans=d.shortest_distance(n)
print(ans if ans!=float("inf") else -1)
### BUGGY CODE ###

n = int(input())
s = list(input())
total = 0
l_c, r_c = 0,0
min = 3*10**5 + 1
for i in range(n):
    left = s[0:i]
    right = s[i+1:n]
    if(left and right):
        l_c = left.count('W')
        r_c = right.count('E')
        total = l_c + r_c
    elif(left):
        l_c = left.count('W')
        total = l_c
    elif(right):
        r_c = right.count('E')
        total = r_c

    if(min > total):
        min = total
        total = 0

print(min)

### FIXED CODE ###

n = int(input())
s = list(input())
r_c = s[1:n].count('E')
min = r_c
for i in range(1,n):
    if(s[i-1] == 'W'):
        r_c += 1
    if(s[i] == 'E'):
        r_c -=1
    if(min > r_c):
        min = r_c
print(min)
### BUGGY CODE ###

from copy import deepcopy
h,w,n = (int(i) for i in input().split())
c1,ans = [[] for i in range(w)],0
for i in range(h):
	s = input()
	for j in range(w): c1[j].append(int(s[j]))
if n<4:
	for i in range(h//2,h):
		for j in range(w):
			c,m,a = deepcopy(c1),0,0
			del c[j][i]
			c[j] = [0]+c[j]
			while 1:
				d = []
				for k in range(i-h,-h,-1):
					k2 = 0
					while k2<w-n+1:
						if c[k2][k] and all(c[k2][k]==c[k2+k3][k] for k3 in range(1,n)):
							b = n
							for k3 in range(k2+n,w):
								if c[k2][k]==c[k3][k]: b+=1
								else: break
							d.append((h+k,k2,b))
							k2+=b
						else: k2+=1
				if d:
					for k,k2,k3 in d:
						a+=(2**m)*c[k2][k]*k3
						for k4 in range(k2,k2+k3): del c[k4][k]
					for k,k2,k3 in d:
						for k4 in range(k2,k2+k3): c[k4] = [0]+c[k4]
				else: break
				m+=1
			ans = max(ans,a)
print(ans)

### FIXED CODE ###

from copy import deepcopy
h,w,n = (int(i) for i in input().split())
c1,ans = [[] for i in range(w)],0
for i in range(h):
	s = input()
	for j in range(w): c1[j].append(int(s[j]))
if n<4:
	if h==30: z = 25
	else: z = h//2
	for i in range(z,h):
		for j in range(w):
			c,m,a = deepcopy(c1),0,0
			del c[j][i]
			c[j].insert(0,0)
			while 1:
				d = []
				for k in range(i-h,-h,-1):
					k2 = 0
					while k2<w-n+1:
						if c[k2][k] and all(c[k2][k]==c[k2+k3][k] for k3 in range(1,n)):
							b = n
							for k3 in range(k2+n,w):
								if c[k2][k]==c[k3][k]: b+=1
								else: break
							d.append((h+k,k2,b))
							k2+=b
						else: k2+=1
				if d:
					for k,k2,k3 in d:
						a+=(2**m)*c[k2][k]*k3
						for k4 in range(k2,k2+k3): del c[k4][k]
					for k,k2,k3 in d:
						for k4 in range(k2,k2+k3): c[k4].insert(0,0)
				else: break
				m+=1
			ans = max(ans,a)
print(ans)
### BUGGY CODE ###

def f(a, b):
    ans = 0
    for i in range(a, b + 1):
        ans = ans ^ i
    return ans

a, b = [int(i) for i in input().split()]
print(f(a, b))

### FIXED CODE ###

def f(x):
    if x % 4 == 0:
        return x
    elif x % 4 == 1:
        return 1
    elif x % 4 == 2:
        return x + 1
    else:
        return 0

a, b = map(int, input().split())
print(f(a-1) ^ f(b))
### BUGGY CODE ###

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



while len(S)!=1:
    S.sort()
    
    
    if S[1]%S[0]==0:
        S.pop(1)
    
    else:
        S[1]=S[1]%S[0]
    if S[0]==1:
        print(1)
        exit()
print(S[0])

### FIXED CODE ###

import math

N=int(input())
S=list(map(int,input().split()))
F=S[0]
for i in range(N-1):
    F=math.gcd(F,S[i+1])

print(F)
### BUGGY CODE ###

a,b=map(int,input().split())
ans=[]
for i in range(a,b):
    for j in range(i+1,b+1):
        z=i*j
        ans.append(z%2019)
print(min(ans))

### FIXED CODE ###

L,R=map(int,input().split())
ans=[]
R=min(R,L+2019)
for i in range(L,R):
    for j in range(i+1,R+1):
        ans.append(i*j%2019)
print(min(ans))
### BUGGY CODE ###

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

ans=1
for x in a:
  ans*=x

if ans>10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

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

if 0 in a:
  print(0)
  exit()

ans=1
for x in a[::-1]:
  ans*=x
  if ans>10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

from collections import deque
s=list(str(input()))
s=deque(s)
q=int(input())
for i in range(q):
    que=list(input().split())
    if len(que)==1:
        s=list(s)
        s=s[::-1]
        s=deque(s)
    else:
        if int(que[1])==1:
            s.appendleft(que[2])
        elif int(que[1])==2:
            s.append(que[2])
s=list(s)
print(''.join(s)) 

### FIXED CODE ###

from collections import deque
s=list(str(input()))
s=deque(s)
q=int(input())
cnt=0
for i in range(q):
    que=list(input().split())
    if len(que)==1:
        cnt+=1
    if len(que)!=1 and cnt%2==0:
        if int(que[1])==1:
            s.appendleft(que[2])
        elif int(que[1])==2:
            s.append(que[2])
    if len(que)!=1 and cnt%2!=0:
        if int(que[1])==1:
            s.append(que[2])
        elif int(que[1])==2:
            s.appendleft(que[2])
if cnt%2!=0:
    s.reverse()
print(''.join(s))
### BUGGY CODE ###

import itertools 

n = int(input())

L = list(map(int,input().split()))

cnt = 0
for a,b,c in itertools.combinations(L,3):
    if a >= b+c:
        continue
    if b >= a+c:
        continue
    if c >= a+b:
        continue
    
    cnt += 1

print(cnt)   

### FIXED CODE ###

import itertools
import bisect

n = int(input())

L = list(map(int,input().split()))

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

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

import itertools

N,C=map(int,input().split())
D=[list(map(int,input().split())) for _ in range(C)]
c=[list(map(int,input().split())) for _ in range(N)]

M=[[] for _ in range(3)]
for i in range(N):
    for j in range(N):
        n=(i+j+2)%3
        M[n].append(c[i][j])

ans=float("inf")
num=[i for i in range(1,C+1)]
for n,m,l in itertools.permutations(num,3):
    n,m,l=int(n),int(m),int(l)
    val=0
    for i in M[0]:
        val+=D[i-1][n-1]
    for j in M[1]:
        val+=D[j-1][m-1]
    for k in M[2]:
        val+=D[k-1][l-1]
    ans=min(ans,val)
print(ans)

### FIXED CODE ###

from collections import defaultdict

N,C=map(int,input().split())
D=[list(map(int,input().split())) for _ in range(C)]
grid=[list(map(int,input().split())) for _ in range(N)]

mod_0=defaultdict(int)
mod_1=defaultdict(int)
mod_2=defaultdict(int)

for i in range(N):
    for j in range(N):
        n=(i+j+2)%3
        if n==0:
            mod_0[grid[i][j]]+=1
        elif n==1:
            mod_1[grid[i][j]]+=1
        else:
            mod_2[grid[i][j]]+=1

ans=float("inf")
for i in range(C):
    for j in range(C):
        if i==j:
            continue
        for k in range(C):
            if k in [i,j]:
                continue

            total=0
            for prev,cnt in mod_0.items():
                total+=D[prev-1][i]*cnt
            for prev,cnt in mod_1.items():
                total+=D[prev-1][j]*cnt
            for prev,cnt in mod_2.items():
                total+=D[prev-1][k]*cnt
            
            ans=min(ans,total)
print(ans)
### BUGGY CODE ###

import math
honsu,hp=map(int , input().split())
huru=[]
nageru=[]
for i in range(honsu):
  a,b=input().split()
  huru.append(int(a))
  nageru.append(int(b))
cou=0
for i in reversed(sorted(nageru)):
  if i>=max(huru):
  	hp-=i
  	cou+=1
  if hp<=0:
    break
if hp>0:
  cou+=math.ceil(hp/max(huru))
print(cou)

### FIXED CODE ###

from math import ceil
 
N, H = map(int, input().split())
a, b = [], []
 
for _ in range(N):
    a_i, b_i = map(int, input().split())
    a.append(a_i)
    b.append(b_i)
 
max_a = max(a)
b = sorted(b, reverse=True)
ans = float('inf')
th_po = 0
 
for i in range(N):
    th_po += b[i]
    
    if H >= th_po:
        ans_cand = i + 1 + ceil((H - th_po) / max_a)
    else:
        ans_cand = i + 1
    
    ans = min([ans, ans_cand])
 
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    a道 = aD[0:iK]
    a鉄道 = aD[iK:]

    d道 = {}
    d鉄道 = {}
    for i in range(1,iN+1):
        d道[i] = {i}
        d鉄道[i] ={i}

    for p,q in a道:
        d道[p].add(q)
        d道[q].add(p)
    for r,s in a鉄道:
        d鉄道[r].add(s)
        d鉄道[s].add(r)

    def fdfs(d,iS):
        dsVisited=set()
        def digRoute(iT):
            for i in d[iT] - dsVisited:
                dsVisited.add(i)
                digRoute(i)
        digRoute(iS)
        return dsVisited

    def buildGroup(d):
        gl = {}
        gidx = {}
        v = set()
        iC = 0
        for i in range(1,iN+1):
            if i in v:
                continue
            else:
                dsList = fdfs(d,i)
                for i in dsList:
                    gidx[i] = iC
                gl[iC]=dsList
                iC += 1
                v = v | dsList
        return (gl,gidx)
    dg鉄道,idxdg鉄道 = (buildGroup(d鉄道))
    dg道,idxdg道 = (buildGroup(d道))
    aRet = []
    for i in range(1,iN+1):
        aRet.append(str(len( dg道[idxdg道[i]] & dg鉄道[idxdg鉄道[i]])))
    print( " ".join(aRet))
解()


### FIXED CODE ###

#Union-Find木の構築
import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        aT = [0]*(iN+1)
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q)
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot #これで Union してるつもり
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): #find みんな小さい方に合わせるならデカい方に合わせてみよう
        if a[i] == i or a[i] == 0:
            if a[i] == 0 : a[i] = i
            return i
        elif i < a[i] :
            a[i] = getRoot(a,a[i])
            return a[i]
    #   else:
    #       print("! ",i,a[i])

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        # いやはやこんなもんもキーになるのか。
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()
### BUGGY CODE ###

import math
import fractions

k=int(input())
tot=0

for i in range(1,k+1):
    for j in range(1,k+1):
        for m in range(1,k+1):
            ans=i
            ans=fractions.gcd(ans,j)
            ans=fractions.gcd(ans,m)
            tot+=ans
print(tot)

### FIXED CODE ###

import math
k= int(input())
tot= 0
for i in range(1, k+1):
    for j in range(1, k+1):
        m = math.gcd(i,j)
        for n in range(1, k+1):
            l = math.gcd(m,n)
            tot += l
print(tot)
### BUGGY CODE ###

import numpy as np
H, W = map(int, input().split())
S = []
ij = np.zeros((H,W), dtype=int)    # .の連続数を格納用

for i in range(H):
    S.append(input())
    cnt = 0
    start = 0
    end = 0
    for j in range(W):
        if S[i][j] == '#':
            ij[i, start:end+1] += cnt
            cnt = 0
        elif j > 0 and S[i][j-1] == '#':    # .のstart
            start = j
            end = j
            cnt = 1
        else:
            end = j
            cnt += 1
        if j == W-1:    # 最後に書き込み
            ij[i, start:end+1] += cnt
            cnt = 0

for j in range(W):
    cnt = 0
    start = 0
    end = 0
    for i in range(H):
        if S[i][j] == '#':
            ij[start:end+1, j] += cnt
            cnt = 0
        elif i > 0 and S[i-1][j] == '#':    # .のstart
            start = i
            end = i
            cnt = 1
        else:
            end = i
            cnt += 1
        if i == H-1:    # 最後に書き込み
            ij[start:end+1, j] += cnt
            cnt = 0

ij = ij - 1  # 自分が2回足されるので、1引く
ans = ij.max()
print(ans)

### FIXED CODE ###

import numpy as np
H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
us = np.zeros((H,W), dtype=int)    # .の連続数を格納用
ds = np.zeros((H,W), dtype=int)    # .の連続数を格納用
ls = np.zeros((H,W), dtype=int)    # .の連続数を格納用
rs = np.zeros((H,W), dtype=int)    # .の連続数を格納用

for h in range(1,H):
    us[h, :] = (us[h-1, :] + 1) * S[h-1, :]
for h in range(H-2, -1, -1):
    ds[h, :] = (ds[h+1, :] + 1) * S[h+1, :]
for w in range(1,W):
    ls[:, w] = (ls[:, w-1] + 1) * S[:, w-1]
for w in range(W-2, -1, -1):
    rs[:, w] = (rs[:, w+1] + 1) * S[:, w+1]

ans = ((us + ds + ls + rs)*S).max() + 1
print(ans)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort(reverse=True)
while len(li)>0:
    ba = li.pop(0)
    if c[ba]>1:
        continue
    #s_ba = math.ceil(math.sqrt(ba))+1
    #index = bisect.bisect_right(li, s_ba)
    tmp_li = li
    #print(ba,tmp_li)
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0
cnt_li = [0]*(10**6+1)

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()

for l in li:
    for x in range(2,10**7):
        if x*l > (10**6):
            break
        else:
            cnt_li[x*l] += 1


while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    if cnt_li[ba] == 0:
        ans += 1
print(ans)