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

from collections import Counter
n = int(input())
A = Counter(list(map(int, input().split())))
A_keys = list(A.keys())
A_keys.sort()
for key in A_keys:
    A_keys = [x for x in A_keys if (x == key or x % key != 0)]
ans = 0
for key in A_keys:
    if A[key] > 1:
        continue
    ans += 1
print(ans)

### FIXED CODE ###

n = input()
*A, = map(int, input().split())
max_A = max(A)
count = {a:0 for a in A}
for a in A:
    count[a] += 1
is_OK = {a:True for a in A}
for a in A:
    i = 2
    if not is_OK[a]:
        continue
    while a * i < max_A + 1:
        is_OK[a * i] = False
        i += 1
ans = 0
for a in A:
    if count[a] == 1 and is_OK[a]:
        ans += 1
print(ans)
### BUGGY CODE ###

from numba import njit

@njit
def calc(A):
    B = [0] * len(A)
    for i in range(len(A)):
        B[max(0,i - A[i])] += 1
        if i + A[i] + 1 < len(A):
            B[i + A[i] + 1] -= 1
    for i in range(1,len(B)):
        B[i] = B[i - 1] + B[i]
    return B
  
import sys
readline=sys.stdin.readline
  
N,K = map(int,readline().split())
A = list(map(int,readline().split()))

for i in range(K):
  A = calc(A)
  if len(set(A)) == 1 and A[0] == N:
    break
print(*A)


### FIXED CODE ###

import sys
readline=sys.stdin.readline

N,K = map(int,readline().split())
A = list(map(int,readline().split()))
def calc(A):
    B = [0] * len(A)
    for i in range(len(A)):
        B[max(0,i - A[i])] += 1
        if i + A[i] + 1 < len(A):
            B[i + A[i] + 1] -= 1
    for i in range(1,len(B)):
        B[i] = B[i - 1] + B[i]
    return B

for i in range(K):
  A = calc(A)
  if len(set(A)) == 1 and A[0] == N:
    print(*A)
    break
else:
  print(*A)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()

    ans = 0
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            A = L[i]
            B = L[j]

            minC = max(A - B, B - A)
            maxC = A + B

            left = bisect_right(L, minC)
            right = bisect_left(L, maxC)

            ans += right - left

            if left <= i < right:
                ans -= 1
            if left <= j < right:
                ans -= 1

    print(ans // 6)


sol()

### FIXED CODE ###

from bisect import bisect_left

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

ans = 0
for i, A in enumerate(L):
    for j, B in enumerate(L[i + 1:], start=i + 1):
        right = bisect_left(L, A + B)
        ans += right - j - 1

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

import sys
INF = 1e9 + 5
def solve(n, k, arr):
    dp = [INF] * n
    dp[0] = 0
    for i, _ in enumerate(arr):
        for j in range(i+1, i+k+1):
            if j == n:
                break
            if j < n:
                dp[j] = min(dp[j], dp[i] + abs(arr[j]-arr[i]))
    return dp[-1]

if __name__ == "__main__":
    f = sys.stdin
    fo = sys.stdout
    n, k = map(int, f.readline().split())
    arr = list(map(int, f.readline().split()))
    result = solve(n, k, arr)
    print(result)


### FIXED CODE ###

import sys
INF = 1e9 + 5
def solve(n, k, ls):
    dp = [0] * n
    dp[1] = abs(ls[0]-ls[1])
    for i in range (2,n):
        dp[i] = min(abs(ls[i] - ls[j]) + dp[j] for j in range(max(0,i-k),i))
    return dp[-1]

if __name__ == "__main__":
    f = sys.stdin
    fo = sys.stdout
    n, k = map(int, f.readline().split())
    arr = list(map(int, f.readline().split()))
    result = solve(n, k, arr)
    print(result)
### BUGGY CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
aa = collections.Counter(a)
ans = 0
num = 0
for k,v in aa.items():
  num = a.count(k)+a.count(k-1)+a.count(k+1)
  ans = max(ans,num)
print(ans)

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]
memo = [0]*(10**5+2)
ans = 1
for i in range(N):
  memo[a[i]] += 1
  memo[a[i]+1] += 1
  memo[a[i]-1] += 1
print(max(memo))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N,= map(int, input().split())
S=[]
su=0
for i in range(N):
    a= input()
    
    if(a in S):
        continue
    S.append(a)
    su+=1
print(su)

### FIXED CODE ###

# coding: utf-8
# Your code here!
N,= map(int, input().split())
S=[]
su=0
for i in range(N):
    a = input()
    S+=[a]    
print(len(set(S)))
### BUGGY CODE ###

N = int(input())
List_Bricks = [int(i) for i in input().split()]
#print(List_Bricks)
Search = 1
Kudaku = 0
i = 0
Boole = False
Count = 0
while len(List_Bricks) != 0:
    if Boole:
        Search = Search + 1
        Boole = False
    elif List_Bricks[0] != Search:
        del List_Bricks[0]
        Kudaku += 1
        Boole = False
        #print(List_Bricks)
    elif List_Bricks[0] == Search:
        del List_Bricks[0]
        Boole = True
        Count = Count + 1
        #print(List_Bricks)
if Count == 0:
    print(-1)
else:
    print(Kudaku)

### FIXED CODE ###

N = int(input())
k = 0
for x in map(int,input().split()):
    if x == k + 1:
        k += 1
print(N-k if k else -1)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = {}
B = [True]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if (N-count)**2 < N : break

for i in range(L):
    if i not in ANS:
        ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS:
            ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if i in ana:
        dp[i] = 0
        ana.pop(len(ana)-1)
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)

### FIXED CODE ###

N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if len(ana) >= 1 and i == ana[-1]:
        dp[i] = 0
        if len(ana) != 0:
            ana.pop(-1)
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)
### BUGGY CODE ###

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

p = {}
t = sorted(list(set(a)))
s = [0]*len(t)
for i in range(len(t)):
  l = a.count(t[i])
  p[t[i]] = l
#print(p)
for i in a:
  s = 0
  x = p[i]
  p[i] -= 1
  for j in t:
    for k in range(p[j]):
      s += k
  print(s)
  p[i] = x
    

### FIXED CODE ###

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

nums = [0]*(n+1)
for i in a:
  nums[i] += 1
  
t = 0
for j in nums:
  t += j*(j-1)//2

for k in a:
  print(t+1-nums[k])
### BUGGY CODE ###

from itertools import product
import copy
H,W,K = list(map(int, input().split()))
A = []
for i in range(H):
  A.append(list(map(int, input())))

#SM = [np.cumsum(A[i]) for i in range(H)]

ANS = []
for pat in product(['0','1'], repeat = H-1):
  res = []
  cnt = 0
  now = copy.copy(A[0])
  for i in range(1,H):
    p = pat[i-1]
    if p == '1':
      res.append(now)
      now = copy.copy(A[i])
      cnt += 1
    else:
      for j in range(W):
        now[j] += A[i][j]
  res.append(now)
  
  wk = [0 for _ in range(len(res))]
  for x in range(W):
    flg = True
    while flg:
      for j in range(len(res)):
        wk[j] += res[j][x]
      if max(wk) > K:
        cnt += 1
        flg = True
        wk = [0 for _ in range(len(res))]
      else:
        break
  ANS.append(cnt)
  
print(min(ANS))

### FIXED CODE ###

from itertools import product
import copy
H,W,K = list(map(int, input().split()))
A = []
for i in range(H):
  A.append(list(map(int, input())))

#SM = [np.cumsum(A[i]) for i in range(H)]

ANS = []
for pat in product(['0','1'], repeat = H-1):
  res = []
  cnt = 0
  now = copy.copy(A[0])
  for i in range(1,H):
    p = pat[i-1]
    if p == '1':
      res.append(now)
      now = copy.copy(A[i])
      cnt += 1
    else:
      for j in range(W):
        now[j] += A[i][j]
  res.append(now)
  
  """  
  print("---")
  print(pat)
  print(res)
  print(cnt)
  """  
  wk2 = [0] * len(res)
  cnt2 = 0
  flg = True
  for x in range(W):
    for j in range(len(res)):
      if res[j][x] > K:
        # 横に割った段階で、すでに最小単位がKを超えてたら実現不可能
        flg = False
        break
      if wk2[j] + res[j][x] > K:
        cnt2 += 1
        wk2 = [0] * len(res)
        break
    for j in range(len(res)):
      wk2[j] += res[j][x]
    if not flg:
      break
      
  if flg:
    ANS.append(cnt + cnt2)
    #print(pat, cnt, cnt2)
print(min(ANS))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    
    L = [A.pop(0)]
    ma = L[0]
    for a in A:
        if ma >= a:
            ma = a
            L.append(ma)
            continue
        for i, l in enumerate(L):
            if l < a:
                L[i] = a
                ma = min(L)
                break
        else:
            L.append(a)
    return len(L)


def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))

    # N = 10**5
    # A = [random.randint(1, 10**9) for _ in range(N)]
    # # A.sort()
    # # A.reverse()
    # print(slv(N, A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv(N, A):
    
    L = [-A.pop(0)]
    ma = L[0]
    for a in A:
        if ma <= -a:
            ma = -a
            L.append(ma)
            continue
        i = bisect.bisect_right(L, -a)
        L[i] = -a
        ma = L[-1]
    return len(L)



def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))


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

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
if n == 2:
    print(max(a))
    exit()
x = [a[0], gcd(a[0], a[1])]
y = [gcd(a[-2], a[-1]), a[-1]]
for i in range(1, n - 2):
    x.append(gcd(x[i], a[i + 1]))
    y.insert(0, gcd(y[0], a[-i - 2]))
ans = max(x[-1], y[0])
for i in range(n - 2):
    ans = max(ans, gcd(x[i], y[i + 1]))
print(ans)


### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
if n == 2:
    print(max(a))
    exit()
x = [a[0], gcd(a[0], a[1])]
for i in range(n - 3):
    x.append(gcd(x[i + 1], a[i + 2]))
ans = x[-1]
y = a[-1]
for i in range(1, n - 1):
    z = gcd(y, a[-i])
    ans = max(ans, gcd(x[-i - 1], z))
    y = z
print(max(ans, gcd(y, a[1])))
### BUGGY CODE ###

N = int(input())
d = sorted(list(map(int, input().split())))
ans = []
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if (d[i] < (d[j] + d[k])) & (d[j] < (d[i] + d[k])) & (d[k] < (d[j] + d[i])):
                ans.append(sorted([d[i], d[j], d[k]]))
            else:
                break
seen = []
ans = [x for x in ans if x not in seen and not seen.append(x)]
print(len(ans))

### FIXED CODE ###

from bisect import bisect_left

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

L.sort()
result = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        result += bisect_left(L, L[i] + L[j]) - j - 1
print(result)
### BUGGY CODE ###

def solve():
    N = int(input())
    X = input()
    X_10 = int(X,2)

    r = X.count("1")
    r0 = r-1
    r1 = r+1
    ans = []
    for i in range(N):
        if X[i] == '0':
            ans.append(f((X_10 % r1 + pow(2, N-1-i)) % r1))
        else:
            if r == 1:
                ans.append(0)
            else:
                ans.append(f((X_10 % r0 - pow(2, N-1-i)) % r0))
    
    print(*ans, sep='\n')

def f(N):
    cnt = 1
    while N != 0:
        N = N % popcount(N)
        cnt += 1
    
    return cnt

def popcount(N):
    b = bin(N)
    cnt = 0
    for i in range(2,len(b)):
        if b[i] == '1':
            cnt += 1

    return cnt

if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    N = int(input())
    X = input()
    X_10 = int(X,2)

    r = X.count("1")
    r0 = r-1
    r1 = r+1
    ans = []
    
    s0 = X_10 % r0 if r != 1 else None
    s1 = X_10 % r1 

    for i in range(N):
        if X[i] == '0':
            ans.append(f((s1 + pow(2,N-1-i,r1)) % r1))
        else:
            if r0 == 0:
                ans.append(0)
            else:
                ans.append(f((s0 - pow(2,N-1-i,r0)) % r0))
    
    print(*ans, sep='\n')

def f(N):
    cnt = 1
    while N != 0:
        N = N % popcount(N)
        cnt += 1
    
    return cnt

def popcount(N):
    b = bin(N)
    cnt = 0
    for i in range(2,len(b)):
        if b[i] == '1':
            cnt += 1

    return cnt

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

import itertools
N = int(input())
L = list(map(int, input().split()))
ans = 0
for x in itertools.combinations(L, 3):
  if x[0] < x[1] + x[2] and x[1] < x[0] + x[2] and x[2] < x[0] + x[1]:
    ans += 1
print(ans)

### FIXED CODE ###

import itertools
import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
LS = sorted(L)
l = len(LS)
for i in range(l):
  for j in range(l):
    if i < j:
      k = bisect.bisect_left(LS,LS[i]+LS[j])
      ans += k-j-1
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(4100000)

def func(array, arr, d):
  for v in arr:
    if array[v[0]] == None:
      d1 = d + v[1]
      array[v[0]] = d1
      arr1 = dic.get(v[0], [])
      
      if not func(array, arr1, d1):
        return False
      
    elif array[v[0]] != d + v[1]:
      return False
    
  return True
      

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

array = [None] * n
dic = {}

for i in range(m):
  l,r,d = map(int, input().split())
  l -= 1
  r -= 1
  
  dic.setdefault(l,[])
  dic.setdefault(r,[])
  dic[l].append((r,d))
  dic[r].append((l,-d))
  
for i in range(n):
  if array[i] != None:
    continue
    
  array[i] = 0
  arr = dic.get(i, [])
  
  if not func(array, arr, 0):
    print('No')
    sys.exit()

print('Yes')    

### FIXED CODE ###

import sys

sys.setrecursionlimit(4100000)

def func(array, arr, d):
  for v in arr:
    if array[v[0]] == None:
      d1 = d + v[1]
      array[v[0]] = d1
      arr1 = dic.get(v[0], [])
      
      if not func(array, arr1, d1):
        return False
      
    elif array[v[0]] != d + v[1]:
      return False
    
  return True
      

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

array = [None] * n
dic = {}

for i in range(m):
  l,r,d = map(int, input().split())
  l -= 1
  r -= 1
  
  dic.setdefault(l,[])
  dic.setdefault(r,[])
  dic[l].append((r,d))
  dic[r].append((l,-d))
  
for i in range(n):
  if array[i] != None:
    continue
    
  array[i] = 0
  arr = dic.get(i, [])
  
  if not func(array, arr, 0):
    print('No')
    sys.exit()

print('Yes')
### BUGGY CODE ###

h, n = map(int, input().split())
a, b = [], []
for _ in range(n):
    i, j = map(int, input().split())
    a.append(i)
    b.append(j)

# DP
l = [0]
for i in range(1,h+1):
    cand = []
    for j in range(n):
        if i - a[j] >= 0 and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
for i in range(h+1, h+max(a)):
    cand = []
    for j in range(n):
        if 0 <= i - a[j] < h and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
l = l[h:]
l = [i for i in l if type(i) == int]
print(min(l))

### FIXED CODE ###

h, n = map(int, input().split())
a, b = [], []
for _ in range(n):
    i, j = map(int, input().split())
    a.append(i)
    b.append(j)

# DP
l = [0]
for i in range(1,h+1):
    cand = []
    for j in range(n):
        if i - a[j] >= 0 and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
for i in range(h+1, h+max(a)):
    cand = []
    for j in range(n):
        if 0 <= i - a[j] < h and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
l = l[h:]
l = [i for i in l if type(i) == int]
print(min(l))
### BUGGY CODE ###

import math


def main():
    """
    H * W 板チョコ3分割
    面積：A B C
    minimize(max(A B C) - min(A B C))

    縦or横がMAX、片方が途中まで
    上記1つと、残りを半分
    残り：面積２以上
    """
    H, W = list(map(int, input().strip().split()))
    # 縦MAX, H>=2より、W-1まで確認
    # 横MAX, H>=2より、W=1のとき３分割できないので、W>=2
    answer = calc_answer(H, W)
    answer = calc_answer(W, H, answer=answer)
    print(answer)


def calc_answer(H, W, answer=None):
    # 縦MAX, H>=2より、W-1まで確認
    if answer is None:
        answer = float("inf")

    for _w in range(1, W):
        # 縦MAXで試す
        S = [
            H * _w,
            H * math.ceil((W - _w) / 2),
            H * int((W - _w) // 2),
        ]
        if not 0 in S:
            S_diff = max(S) - min(S)
            #print(H, _w, S, S_diff, answer, sep="\t")
            answer = min(answer, S_diff)

        # 横MAXで縦分割
        for _h in range(1, H):
            S = [
                H * _w,
                (W - _w) * _h,
                (W - _w) * (H - _h),
            ]
            if not 0 in S:
                S_diff = max(S) - min(S)
                #print(_h, _w, S, S_diff, answer, sep="\t")
                answer = min(answer, S_diff)

    return answer

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math


def main():
    """
    H * W 板チョコ3分割
    面積：A B C
    minimize(max(A B C) - min(A B C))

    縦or横がMAX、片方が途中まで
    上記1つと、残りを半分
    残り：面積２以上
    """
    H, W = list(map(int, input().strip().split()))
    # 縦MAX, H>=2より、W-1まで確認
    # 横MAX, H>=2より、W=1のとき３分割できないので、W>=2
    answer = calc_answer(H, W)
    answer = calc_answer(W, H, answer=answer)
    print(answer)


def calc_answer(H, W, answer=None):
    if answer is None:
        answer = float("inf")

    for _w in range(1, math.ceil(W / 2) + 1):
        # 縦MAXで試す
        S = [
            H * _w,
            H * math.ceil((W - _w) / 2),
            H * int((W - _w) // 2),
        ]
        if not 0 in S:
            S_diff = max(S) - min(S)
            #print(H, _w, S, S_diff, answer, sep="\t")
            answer = min(answer, S_diff)

        # 横MAXで縦分割
        S = [
            H * _w,
            (W - _w) * math.ceil(H / 2),
            (W - _w) * int(H // 2),
        ]
        if not 0 in S:
            S_diff = max(S) - min(S)
            #print(_h, _w, S, S_diff, answer, sep="\t")
            answer = min(answer, S_diff)

    return answer

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

import sys
from math import gcd
from functools import reduce

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def lcm(a, b):
    return a * b // gcd(a, b)


def main():
    N, *A = map(int, read().split())

    l = reduce(lcm, A)

    ans = 0
    for a in A:
        ans = (ans + l // a) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from math import gcd
from functools import reduce

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def lcm(a, b):
    return a // gcd(a, b) * b


def main():
    N, *A = map(int, read().split())

    ans = 0
    l = 1
    for a in A:
        l, l_prev = lcm(l, a), l
        ans = (ans * (l // l_prev) % MOD + l // a) % MOD

    print(ans)
    return


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

# -*- coding: utf-8 -*-

def abc159d(n, arr):
    dic = {}
    for a in arr:
        if a in dic:
            dic[a] += 1
        else:
            dic[a] = 1
    
    # delete non-paired ball
    # del_list = []
    # for k, val in dic.items():
    #     if val == 1:
    #         del_list.append(k)
    # for item in del_list:
    #     del dic[item]

    ans = []
    for a in arr:
        sum = 0
        for k, val in dic.items():
            n = val
            if k == a:
                n -= 1

            sum += n * (n-1) // 2

        ans.append(sum)

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    arr = input().split(" ")
    
    ans = abc159d(n, arr)
    
    # output
    for a in ans:
        print(a)
# else:
    # do nothing


### FIXED CODE ###

# -*- coding: utf-8 -*-

def abc159d(n, arr):
    dic = {}
    for a in arr:
        if a in dic:
            dic[a] += 1
        else:
            dic[a] = 1
    
    # delete non-paired ball
    del_list = []
    for k, val in dic.items():
        if val == 1:
            del_list.append(k)
    for item in del_list:
        del dic[item]

    typ_ans = 0
    for val in dic.values():
        typ_ans += val * (val-1) // 2
    
    ans = []
    for a in arr:
        sum = typ_ans
        if a in dic:
            sum -= dic[a] * (dic[a]-1) // 2
            new_val = dic[a] - 1
            sum += new_val * (new_val-1) // 2

        ans.append(sum)

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    arr = input().split(" ")
    
    ans = abc159d(n, arr)
    
    # output
    for a in ans:
        print(a)
# else:
    # do nothing