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

import sys
def input(): return sys.stdin.readline().rstrip()
def prime_fact(m):
    pf={}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    return pf

def main():
    n=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    p_lis={}
    p_a_lis=[]
    for a in A:
        p_a_lis.append(prime_fact(a))
        for key in p_a_lis[-1]:
            if not p_lis.get(key,False) or p_lis[key]<p_a_lis[-1][key]:
                p_lis[key]=p_a_lis[-1][key]
    ans=0
    for i,a in enumerate(A):
        b=1
        for key in p_lis:
            b=(b*key**(p_lis[key]-p_a_lis[i].get(key,0)))%mod
        ans=(ans+b)%mod
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve: #区間[2,n]の値の素因数分解
    def __init__(self,n=1):
        self.primes=[]
        self.f=[0]*(n+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        for i in range(2,n+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,n+1,i):
                if not self.f[j]:
                    self.f[j]=i  # 最小の素因数を代入
    def is_prime(self, x):
        return self.f[x]==x
    def prime_fact(self,x): # 素因数分解の昇順リスト, {2:p,3:q,5:r,...}
        fact_dict=dict()
        while x!=1:
            p=self.f[x]
            fact_dict[p]=fact_dict.get(p,0)+1
            x//=self.f[x]
        return fact_dict

def main():
    n=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    p_lis={}
    Prime=Sieve(10**6+5)
    for a in A:
        f=Prime.prime_fact(a)
        #print(f)
        for key in f:
            p_lis[key]=max(p_lis.get(key,0),f[key])
    lcm=1
    #print(p_lis)
    for key in p_lis:
        lcm=(lcm*pow(key,p_lis[key],mod))%mod
    ans=0
    #print(lcm)
    for a in A:
        b=lcm*pow(a,mod-2,mod)%mod
        ans=(ans+b)%mod
    print(ans)


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

#python3
n=int(input())
a=[int(i) for i in input().split()]
MOD = int(1e9+7)
ans=0
for k in range(60):
  x=0
  for i in range(n):
    if(a[i]>>k)&1:
      x+=1
  contribute = x*(n-x)*(1<<k)
  ans+=contribute
print(ans%MOD)

### FIXED CODE ###

#python3
import numpy as np
N = int(input())
A = np.array([int(_) for _ in input().split()])
mod = 10**9 + 7
ans = 0
for b in range(60):
    B = (A >> b) & 1
    M = np.count_nonzero(B)
    ans += 2**b * M * (N - M)
    ans %= mod
print(ans)
### BUGGY CODE ###

n,k = map(int, input().split())
h = list(map(int, input().split()))
a = [0]*n
if k > n:
    k = n
for i in range(1,k):
    a[i] = float('inf')
    for j in range(1,i+1):
        a[i] = min(a[i], a[i-j] + abs(h[i]-h[i-j]))
for i in range(k,n):
    a[i] = float('inf')
    for j in range(1,k+1):
        a[i] = min(a[i], a[i-j] + abs(h[i]-h[i-j]) )
print(a[n-1])

### FIXED CODE ###

import numpy as np
n,k = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.zeros(n, dtype = int)
for i in range(1,n):
    s = max(0,i-k)
    dp[i] = min(dp[s:i] + np.abs(h[i] -h[s:i]))
print(dp[-1])
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    dp = [True for i in range(a[-1] + 1)]
    prev = -1
    ans = 0
    for i in a:
        if prev == i:
            dp[i] = False
            continue
        zzz = i * 2
        while zzz <= a[-1]:
            if zzz in a:
                dp[zzz] = False
            zzz += i

        prev = i

    for i in a:
        if dp[i]:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

c = Counter(a)
b = [k for k, v in c.items() if v == 1]
b.sort()
d = {b: i for i, b in enumerate(b)}

gg = [True] * len(b)
mx = 10 ** 6 + 1
for i in c.keys():
    for j in range(2 * i, mx, i):
        if j in d:
            gg[d[j]] = False

print(sum(gg))
### BUGGY CODE ###

import math
n=int(input())
result=0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      result+=(math.gcd(math.gcd(i,j),k))
print(result)

### FIXED CODE ###

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

N, M = map(int, input().split())
A = []
sumcost = 0
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
k = 0
A.sort()
while M-k > A[0][1]:
    sumcost += A[0][0]*A[0][1]
    k += A[0][1]
    A.pop(0)
sumcost += A[0][0]*(M-k)

print(sumcost)

### FIXED CODE ###

N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
A.sort()
sumcost = 0
for i in range(M):
    sumcost += A[0][0]
    A[0][1] -= 1
    if A[0][1] < 1:
        A.pop(0)

print(sumcost)
### BUGGY CODE ###

import copy

n, m = [int(i) for i in input().split()]
ans = []
a = list(map(int, input().split()))
for i in range(len(a)):
    ans.append([1, a[i]])
b = []
c = []
for i in range(m):
    d, e = [int(i) for i in input().split()]
    ans.append([d, e])

ans1 = sorted(ans, key=lambda x: x[1], reverse = True)

ans2 = []
for i in range(len(ans1)):
    for j in range(ans1[i][0]):
        ans2.append(ans1[i])

ans3 = []
for i in range(n):
    ans3.append(ans2[i][1])
print(sum(ans3))

### FIXED CODE ###

import copy

n, m = [int(i) for i in input().split()]
ans = []
a = list(map(int, input().split()))
for i in range(len(a)):
    ans.append([1, a[i]])
for i in range(m):
    d, e = [int(i) for i in input().split()]
    ans.append([d, e])

ans1 = sorted(ans, key=lambda x: x[1], reverse = True)
cnt = 0
ans2 = 0
k = 0
while cnt < n:
    ans2 += ans1[k][0] * ans1[k][1]
    cnt += ans1[k][0]
    k += 1
ans2 -= (cnt - n) * ans1[k-1][1]
print(ans2)
### BUGGY CODE ###

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

#リストをソート
a = sorted(a)
b = sorted(b)
c = sorted(c)

# x以上のイテレータを
def lower_bound(arr , x):
    l = 0
    r = len(c)
    for j in range(100):
        mid = (l + r) // 2
        # print(l , r , mid)
        if x <= arr[mid]:
            r = mid
        else:
            l = mid
    return r


count = 0
for i in range(n):
    a_count = lower_bound(a , b[i])
    c_count = len(c) - lower_bound(c , b[i] + 1)
    count += a_count * c_count

print(count)


### FIXED CODE ###

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

#リストをソート
a = sorted(a)
b = sorted(b)
c = sorted(c)

# x以上のイテレータを
def lower_bound(arr , x):
    l = 0
    r = len(c)
    for j in range(30):
        mid = (l + r) // 2
        # print(l , r , mid)
        if x <= arr[mid]:
            r = mid
        else:
            l = mid
    return r


count = 0
for i in range(n):
    a_count = lower_bound(a , b[i])
    c_count = len(c) - lower_bound(c , b[i] + 1)
    count += a_count * c_count

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

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

mod = 10**9 + 7

if n == 1:
    ans = 2 * C[0]
    ans %= mod
    print(ans)
    exit()


ans = 0
pattern = 2 ** (n-1)
C.sort(reverse=True)
for c in C:
    ans += (c * pattern) % mod
    pattern += 2 ** (n-2)
    ans %= mod

print(ans*(2**n) % mod)

### FIXED CODE ###

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

mod = 10**9 + 7

if n == 1:
    ans = 2 * C[0]
    ans %= mod
    print(ans)
    exit()


ans = 0
pattern = 2 ** (n-1) % mod
d = 2 ** (n-2) % mod
C.sort(reverse=True)
for c in C:
    ans += (c * pattern) % mod
    pattern += d
    pattern %= mod
    ans %= mod

print(ans*(2**n) % mod)
### BUGGY CODE ###

from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
a = heapify(A)

for _ in range(M):
    B, C = map(int, input().split())
    for _ in range(B):
        m = heappop(A)
        heappush(A, max(m, C))
        if m > C:
            break

print(sum(A))

### FIXED CODE ###

from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
B = [0] * M
C = [0] * M
for i in range(M):
    B[i], C[i] = map(int, input().split())

cb = sorted(zip(C, B), reverse=True)

cnt = 0
exchange = []
for c, b in cb:
    exchange.extend([c] * b)
    cnt += b
    if cnt >= N:
        break

exchange.sort()

for _ in range(len(exchange)):
    m = heappop(A)
    heappush(A, max(m, exchange.pop()))

print(sum(A))
### BUGGY CODE ###

N, M = map(int, input().split())
i = 1
lis = []
while M//i>=N:
  if M % i == 0:
    ans = i
  i += 1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
i = 1
lis = []
while M//i>=N and i<=M**0.5:
  if M % i == 0:
    lis.append(i)
  i += 1
for l in lis[::-1]:
  ans = M//l
  if M//ans>=N:
    lis.append(ans)
print(lis[-1])
### BUGGY CODE ###


n,k=[int(i) for i in input().split()]
p=[(int(i)+1)/2 for i in input().split()]


ans=0
for i in range(n-k+1):
    sum_max=0
    for j in range(i,i+k):
        sum_max+=p[j]
    ans=max(ans,sum_max)
print(ans)

### FIXED CODE ###

n,k=[int(i) for i in input().split()]
p=[(int(i)+1)/2 for i in input().split()]

ans=0
sum_num=sum(p[:k])
for i in range(n-k+1):
    if i==0:
        sum_num = sum(p[:k])
    else:
        sum_num+=p[i+k-1]-p[i-1]
    ans=max(ans,sum_num)
print(ans)
### BUGGY CODE ###

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

# sum_first  = sum(a)

for i in bc:
    a = [i[1] if j==i[0] else j for j in a]
    # print(a)
    print(sum(a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
query = [list(map(int,input().split())) for _ in range(q)]

all_sum  = sum(a)

cnt = {}
for i in a:
    if i not in cnt:
        cnt[i] = 0
    cnt[i] += 1

for (b, c) in query:
    if b in cnt:
        all_sum -= b * cnt[b]
        all_sum += c * cnt[b]
        if c not in cnt:
            cnt[c]=0 
        cnt[c] += cnt[b]
        cnt[b] = 0
    print(all_sum)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split())) 
ans = 1
for i in range(0,N):
    ans = ans * A[i]
if ans > pow(10,18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split())) 
ans = 1
ikiti = pow(10,18)
if 0 in A:
    print(0)
else:
    ikiti = pow(10,18)
    for i in range(0,N):
        ans = ans * A[i]
        if ans > ikiti:
            print(-1)
            break
    if ans <= ikiti:
        print(ans)
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
c = "@" * (W+2)
for _ in range(H):
	c += "@" + input() + "@"
c += "@" * (W+2)
#c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**6+5
dist = [INF for _ in range((W+2) * (H+2))]
dist[sh*(W+2)+sw] = 0
q = deque()
q.append(sh*(W+2)+sw)
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	l = q.popleft()
	i, j = l//(W+2), l%(W+2)
	for di, dj in zip(DI, DJ):
		for k in range(1, K+1):
			ii, jj = i+di*k, j+dj*k
			if c[ii*(W+2)+jj] == "." and dist[ii*(W+2)+jj] > dist[i*(W+2)+j]:
				dist[ii*(W+2)+jj] = dist[i*(W+2)+j] + 1
				if ii == gh and jj == gw:
					print(dist[ii*(W+2)+jj])
					sys.exit()
				q.append(ii*(W+2) + jj)
			else:
				break
print(-1)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**6+5
dist = [[INF for _ in range(W+2)] for _ in range(H+2)]
dist[sh][sw] = 0
q = deque()
q.append(sh*(W+2)+sw)
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	l = q.popleft()
	i, j = l//(W+2), l%(W+2)
	for di, dj in zip(DI, DJ):
		for k in range(1, K+1):
			ii, jj = i+di*k, j+dj*k
			if c[ii][jj] == "@":
				break
			if dist[ii][jj] <= dist[i][j]:
				break
			if dist[ii][jj] > dist[i][j] + 1:
				dist[ii][jj] = dist[i][j] + 1
				if ii == gh and jj == gw:
					print(dist[ii][jj])
					sys.exit()
				q.append(ii*(W+2) + jj)
print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N = int(input())
XY = [tuple(int(x) for x in input().split()) for _ in range(N)]
XY.sort() # X ascending
X,Y = zip(*XY)
Y_rank = {x:i for i,x in enumerate(sorted(Y),1)}

def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree,x):
    ret = 0
    while x:
        ret += tree[x]
        x -= x & (-x)
    return ret

pow2 = [1]
for _ in range(N):
    pow2.append(pow2[-1] * 2 % MOD)

answer = 0
tree = [0] * (N+1)
for L,y in enumerate(Y):
    y = Y_rank[y]
    R = N - 1 - L
    D = y - 1
    U = N - 1 - D
    LD = 0
    x = y
    while x:
        LD += tree[x]
        x -= x & (-x)
    while y <= N:
        tree[y] += 1
        y += y & (-y)
    LU = L - LD
    RD = D - LD
    RU = R - RD
    # bounding box が自分自身を含むような集合を数える
    # 全体から引く
    cnt = pow2[N]
    cnt -= pow2[L]
    cnt -= pow2[R]
    cnt -= pow2[D]
    cnt -= pow2[U]
    cnt += pow2[LD]
    cnt += pow2[LU]
    cnt += pow2[RD]
    cnt += pow2[RU]
    cnt -= 1
    answer += cnt

answer %= MOD

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]
XY.sort() # X ascending
X,Y = zip(*XY)
Y_rank = {x:i for i,x in enumerate(sorted(Y),1)}

def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree,x):
    ret = 0
    while x:
        ret += tree[x]
        x -= x & (-x)
    return ret

pow2 = [1]
for _ in range(N):
    pow2.append(pow2[-1] * 2 % MOD)

answer = 0
tree = [0] * (N+1)
for L,(x,y) in enumerate(XY):
    y = Y_rank[y]
    R = N - 1 - L
    D = y - 1
    U = N - 1 - D
    LD = BIT_sum(tree,y)
    BIT_update(tree,y)
    LU = L - LD
    RD = D - LD
    RU = R - RD
    # bounding box が自分自身を含むような集合を数える
    # 全体から引く
    cnt = pow2[N]
    cnt -= pow2[L]
    cnt -= pow2[R]
    cnt -= pow2[D]
    cnt -= pow2[U]
    cnt += pow2[LD]
    cnt += pow2[LU]
    cnt += pow2[RD]
    cnt += pow2[RU]
    cnt -= 1
    answer += cnt

answer %= MOD

print(answer)
### BUGGY CODE ###

N = int(input())
A = [int(_) for _ in input().split()]

accumulation_plus = [A[0]]
accumulation_xor = [A[0]]

count = 0

for A_i in A[1:]:
    A_plus = accumulation_plus[-1] + A_i
    accumulation_plus.append(A_plus)

    A_xor = accumulation_xor[-1] ^ A_i
    accumulation_xor.append(A_xor)

    if A_plus == A_xor:
        count += 1

accumulation_plus_box = []
accumulation_xor_box = []

for A_i in A:
    for ac_plus, ac_xor in zip(accumulation_plus, accumulation_xor):
        A_plus_minus = ac_plus - A_i
        accumulation_plus_box.append(A_plus_minus)

        A_xor_minus = ac_xor ^ A_i
        accumulation_xor_box.append(A_xor_minus)

        if A_plus_minus == A_xor_minus:
            count += 1

    accumulation_plus = accumulation_plus_box[1:]
    accumulation_xor = accumulation_xor_box[1:]
    accumulation_plus_box = []
    accumulation_xor_box = []

print(count  - N + 1)


### FIXED CODE ###

N = int(input())
A = [int(_) for _ in input().split()]

r = 0
l_r_max = []
A_plus = 0
A_xor = 0
flag = 0

for l in range(N):
    while r < N:
        A_plus += (A[r] if flag == 0 else -A[l - 1])
        A_xor ^= (A[r] if flag == 0 else A[l - 1])

        if A_plus == A_xor:
            r += 1
            flag = 0
            continue
        else:
            flag = 1
            break

    l_r_max.append(r - l)

print(sum(l_r_max))
### BUGGY CODE ###

n = int(input())
s = [[int(c) for c in input().strip()] for _ in range(n)]

def bfs(s, start):
    lengths = {start: 0}
    plan = [(i, 1) for i, c in enumerate(s[start]) if c == 1]
    while len(plan) > 0:
        vertex, length = plan.pop(0)
        if vertex in lengths:
            if (lengths[vertex] - length) % 2 != 0:
                return -1
        else:
            lengths[vertex] = length
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1 and i not in lengths])
    return max(lengths.values())

bfs_result = 0
for start in range(n):
    res = bfs(s, start)
    if res < 0:
        bfs_result = -2
        break
    elif res > bfs_result:
        bfs_result = res
print(bfs_result + 1)

### FIXED CODE ###

from collections import deque

n = int(input())
s = [[int(c) for c in input().strip()] for _ in range(n)]

def bfs(s, start):
    plan = deque([(start, 0)])
    lengths = {}
    while len(plan) > 0:
        vertex, length = plan.popleft()
        if vertex in lengths:
            if (lengths[vertex] - length) % 2 != 0:
                return -1
        else:
            lengths[vertex] = length
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1 and i not in lengths])
    return max(lengths.values())

bfs_result = 0
for start in range(n):
    res = bfs(s, start)
    if res < 0:
        bfs_result = -2
        break
    elif res > bfs_result:
        bfs_result = res
print(bfs_result + 1)
### BUGGY CODE ###

def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    #a,bには下限と上限、valueにはOKな範囲のときはTrue、そうでないときにFalseを返す関数を入れる
    #limは下限を知りたいときはlower、上限を知りたいときはupperを入れる
    def b_search(a,b,value,lim):
        if lim=='upper':
            while True:
                med=(a+b)//2
                if a==b:return a
                elif a+1==b:
                    if value(b):return b
                    else:return a
                elif value(med):a=med
                else:b=med-1
        else:
            while True:
                med=(a+b)//2
                if a==b:return a
                if a+1==b:
                    if value(a):return a
                    else:return b
                elif value(med):b=med
                else:a=med+1
    
    n,q=map(int,input().split())
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            b=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            b=br(a,ini+dist)-bl(a,ini-dist)
        if k>=b:
            return True
        return False

    for i in x:
        ini=i
        k=b_search(1,n//2+1,check,"lower")
        print(aac[-1]-aac[-k-1]+aac2[-k-1])

main()

### FIXED CODE ###

def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            return k>=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            return k>=br(a,ini+dist)-bl(a,ini-dist)
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    ix=sorted([[i,j] for i,j in enumerate(x)],key=lambda x:x[1])
    ans=[0]*q
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))
    k=nn

    for i,ini in ix:
        l=1
        u=k
        while l+1<u:
            med=(l+u)//2
            if check(med):u=med
            else:l=med+1
        if check(l):k=l
        else:k=u
        ans[i]=aac[-1]-aac[-k-1]+aac2[-k-1]
    for i in ans:
        print(i)
main()
### BUGGY CODE ###

import sys
def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    count1 = 0
    count2 = 0
    d = []
    l = {}
    
    for i in range(N):
        a,b = map(int, input().split())
        if not a in d:
            d.append(a)
            l[a] = b
        else:
            l[a] += b
        count1 += b

    d.sort()
    for i in d:
        count2 += l[i]
        if count2 >= K:
            print(i)
            break
        

        

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import defaultdict
def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    count1 = 0
    count2 = 0
    d = []
    l = defaultdict(int)
    
    for i in range(N):
        a,b = map(int, input().split())
        l[a] += b


    for i, j in sorted(l.items()):
        count2 += j
        if count2 >= K:
            print(i)
            break
        

        

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

s = input()
t = input()
# dp[i][j] = LCS(s[:i+1],t[:j+1])
dp = [ [""]*(len(t)+1)  for _ in range(len(s)+1) ]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        incStr = s[i-1] if s[i-1]==t[j-1] else ""
        comp = [ dp[i][j-1],dp[i-1][j-1]+incStr,dp[i-1][j]]
        dp[i][j] = comp[comp.index(max(comp,key=lambda x: len(x)))]


print(dp[len(s)][len(t)])

### FIXED CODE ###

import sys

s = sys.stdin.readline()
t = sys.stdin.readline()

# dp[i][j] = LCS(s[:i],t[:j])
sLen, tLen = len(s),len(t),
dp = [ [( 0 , -1 )]*(tLen+1)  for _ in range(sLen+1) ]
for i in range(1,sLen+1):
    for j in range(1,tLen+1):
        comp = [ dp[i][j-1][0],dp[i-1][j-1][0]+int(s[i-1]==t[j-1]),dp[i-1][j][0]]
        argmax = comp.index(max(comp))
        dp[i][j] = ( comp[argmax] , argmax )

ans = ""
i,j = sLen, tLen
for _ in range(sLen+tLen):
    if dp[i][j][1] == 0:
        j -= 1
    elif dp[i][j][1] == 1:
        ans += s[i-1]
        i -= 1
        j -= 1
    elif dp[i][j][1] == 2:
        i -= 1
    else:
        break

print(ans[::-1])
### BUGGY CODE ###

N=int(input())
I=[int(input()) for i in range(N)]
for j in range(N):
	X=int(I[j])
	I.remove(I[j])
	print(max(I))
	I.insert(j,X)

### FIXED CODE ###

N=int(input())
I=[int(input()) for i in range(N)]
r=max(I)
if I.count(r)>=2:
	for j in range(N):
		print(r)
else:
	for k in range(N):
		X=int(I[k])
		if X!=r:
			print(r)
		else:
			I.remove(I[k])
			print(max(I))
			I.insert(k,X)
### BUGGY CODE ###

p = int(input())
a = list(map(int,input().split()))
mod = p
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def inv(x):
  return pow(x,mod-2,mod)
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
ans = [0]*p
for i in range(p):
  if a[i]:
    ans[0] += 1
    for j in range(p):
      ans[-j-1] -= ((-1)**(j%2))*cmb(p-1,j)*pow(i,j,p)
      ans[-j-1] %= mod
print(*ans)

### FIXED CODE ###

p = int(input())
a = list(map(int,input().split()))
mod = p
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def inv(x):
  return pow(x,mod-2,mod)
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
ans = [0]*p
for i in range(p):
  if a[i]:
    ans[0] += 1
    const = 1
    for j in range(p):
      ans[-j-1] -= ((-1)**(j%2))*cmb(p-1,j)*const
      ans[-j-1] %= mod
      const *= i
      const %= mod
print(*ans)
### BUGGY CODE ###

from collections import Counter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = Counter()
    count.update(A)
    sum_ = 0
    for i in count.values():
        sum_ += i*(i-1)/2

    for i in range(len(A)):
        remain = A[:i] + A[i+1:]
        took_count = count[A[i]]
        sub = took_count - 1
        print(int(sum_ - sub))

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = Counter(A)
    sum_ = sum([v*(v-1)/2 for v in count.values()])

    for i in range(len(A)):
        took_count = count[A[i]]
        sub = took_count - 1
        print(int(sum_ - sub))

if __name__ == '__main__':
    main()