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

import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
A = inpl()

ss = sum(A)
s = 0
for i in range(len(A)):
    s = (s + sum(A[i+1:])*A[i]) % mod

print(s)

### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
A = inpl()

sss = list(itertools.accumulate(A))
ss = sum(A)
s = 0
for i in range(len(A)-1):
    s = (s + ((ss-sss[i]) * A[i])) % mod

print(s)
### BUGGY CODE ###

def main():
    N = int(input())
    X = tuple(map(int,input().split()))
    MOD = 10 ** 9 + 7
    goal = X[-1]
    ans = goal - X[0]
    x = 1
    count = 2
    for i in X[1:N-1]:
       tmp = goal - i
       ans = ((ans * count % MOD) + ((x * tmp) % MOD)) % MOD
       x *= count % MOD
       count += 1
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    X = list(map(int,input().split()))
    MOD = 10 ** 9 + 7
    goal = X[-1]
    ans = goal - X[0]
    fact = [1]
    fact_inv = [1]
    for i in range(10**5+5):
        new_fact = fact[-1]*(i+1)%MOD
        fact.append(new_fact)
    count = 1
    for i in range(1,N-1):
        count += 1
        tmp = goal - X[i]
        ans = ((ans * count) + ((fact[i] * tmp))) % MOD  
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

if __name__=="__main__":
    N = int(input())
    l = list(map(int,input().split(" ")))
    count = 0
    visited_list = []
    for i in l:
        if i not in visited_list:
            visited_list.append(i)
            if l.count(i)<i:
                count+=l.count(i)
            if l.count(i)>i:
                count+=l.count(i)-i
    print(count)

### FIXED CODE ###

def main():
    N = int(input())
    l = list(map(int,input().split(" ")))
    dic = {}
    count = 0
    for i in l:
        try:
            dic[i] += 1
        except Exception:
            dic[i] = 1

    for j in dic.items():
        count += j[1] - j[0] if j[1] >= j[0] else j[1]
    print(count)


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

from collections import Counter
N = int(input())
S = []
ans = 0
for i in range(N):
  s = input()
  S.append(s)
for i in range(N-1):
  for j in range(i+1,N):
    A = [False]*10
    B = [False]*10
    for k in range(10):
      for l in range(10):
        if S[i][k] == S[j][l] and A[k] == False and B[l] == False:
          A[k] = True
          B[l] = True
          continue
    if all(A):
      ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
memo = {}
ans = 0
for i in range(N):
  s = list(input())
  s.sort()
  s = str(s)
  if s in memo.keys():
    memo[s] += 1
  else:
    memo[s] = 1
for v in memo.values():
  if v >= 2:
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
a, b, q = map(int, input().split())
shrine = [int(input()) for _ in range(a)]
temple = [int(input()) for _ in range(b)]

inf = 10**18
for _ in range(q):
    ans = inf
    x = int(input())
    index_s = bisect_left(shrine, x)
    index_t = bisect_right(temple, x)
    for i in range(index_s-1, index_s+1):
        if i == a or i < 0:
            continue
        s = shrine[i]
        i_t = bisect_left(temple, s)
        
        if i_t != 0:
            ans = min(
                ans,
                abs(x - s) + abs(s - temple[i_t - 1])
            )

        if i_t <= b-1:
            t1 = temple[i_t]
            ans = min(
                ans,
                abs(x - s) + abs(s - t1),
            )

    for i in range(index_t-1, index_t+1):
        if i == b or i < 0:
            continue
        t = temple[i]
        i_s = bisect_left(shrine, t)
        if i_s != 0:
            s0 = shrine[i_s - 1]
            ans = min(
                ans,
                abs(x - t) + abs(t - s0)
            )
            
        if i_s <= a-1:
            s1 = shrine[i_s]
            ans = min(
                ans,
                abs(x - t) + abs(t - s1),
            )

    print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
a, b, q = map(int, input().split())
inf = 10**18
shrine = [-inf] + [int(input()) for _ in range(a)] + [inf]
temple = [-inf] + [int(input()) for _ in range(b)] + [inf]

for _ in range(q):
    ans = inf
    x = int(input())
    index_s = bisect_left(shrine, x)
    index_t = bisect_right(temple, x)
    for i in range(index_s-1, index_s+1):
        s = shrine[i]
        i_t = index_t
        t0, t1 = temple[i_t-1], temple[i_t]
        ans = min(
            ans,
            abs(x - s) + abs(s - t0),
            abs(x - s) + abs(s - t1),
        )

    for i in range(index_t-1, index_t+1):
        t = temple[i]
        i_s = index_s
        s0 = shrine[i_s - 1]
        s1 = shrine[i_s]
        ans = min(
            ans,
            abs(x - t) + abs(t - s0),
            abs(x - t) + abs(t - s1),
        )

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

import fractions
from functools import reduce

N = int(input())
A = list(map(int,input().split()))
g_max = 0
for i in range(N):
    B = A.copy()
    B[i:i+1] = []
    g = reduce(fractions.gcd,B)
    if g_max < g:
        g_max = g
print(g_max)

### FIXED CODE ###

def gcd(x,y):
    while y != 0:
        x,y = y,x%y
    return x
n = int(input())
a = list(map(int,input().split()))

L,R = [0],[0]
for i in range(1,n+1): #L[i]は左i個,R[i]は右i個
    L.append(gcd(L[-1],a[i-1]))
    R.append(gcd(R[-1],a[n-i]))
print(max(gcd(L[i],R[n-i-1]) for i in range(n)))
### BUGGY CODE ###

S = list(input())
n = len(S)
dp = [[0] * 13 for _ in range(n + 1)]

MOD = 10 ** 9 + 7

def solve():
    res = 0
    dp[0][0] = 1
    for i in range(n): #n文字順番に確かめる
        if S[i] == '?': #i文字目が自由のとき
            c = -1
        else:
            c = int(S[i])
        
        for j in range(10):
            if c != -1 and c != j:
                continue
            for k in range(13):
                dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
        
        for j in range(13):
            dp[i + 1][j] %= MOD
    # print (dp)
    res = dp[n][5]
    return res

print (solve())



### FIXED CODE ###

S = list(input())
n = len(S)
dp = [[0] * 13 for _ in range(n + 1)]

MOD = 10 ** 9 + 7

def solve():
    res = 0
    dp[0][0] = 1
    for i in range(n): #n文字順番に確かめる
        if S[i] == '?': #i文字目が自由のとき
            c = -1
        else:
            c = int(S[i])
        
        for j in range(10):
            if c != -1 and c != j:
                continue
            for k in range(13):
                dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
        
        for j in range(13):
            dp[i + 1][j] %= MOD
    # print (dp)
    res = dp[n][5]
    return res

print (solve())
### BUGGY CODE ###

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

max = 0

for i in range(0,N-K+1) :
    total = sum(list_p[i:i+K])
    if total > max :
        max = total

print((max+K)/2)


### FIXED CODE ###

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

total = sum(list_p[0:K])
max = total

for i in range(0,N-K) :
    total = total - list_p[i] + list_p[i+K]
    if total > max :
        max = total

print((max+K)/2)
### BUGGY CODE ###

from collections import deque

Y, X = map(int,input().split())
# sy, sx = map(int, input().split())
# gy, gx = map(int, input().split())
sy,sx = 1,1
gy,gx = Y,X
s = [["#"]*(X+2) for _ in range(Y+2)]
for y in range(Y):
    s[y+1] = list("#"+input()+"#")
inf = Y*X
c = [[inf]*X for _ in range(Y)]
c[sy-1][sx-1] = 0
q = deque([(sy-1, sx-1)])

while q:
    y,x = q.popleft()
    cost = c[y][x]
    for dx,dy in [[-1,0],[1,0],[0,0],[0,-1],[0,1]]:
        x2 = x+dx
        y2 = y+dy
        if s[y2+1][x2+1] == "." and c[y2][x2] > cost:
            c[y2][x2] = cost+1
            q.appendleft((y2,x2))
if c[gy-1][gx-1] == inf:
    print("-1")
else:
    dots = 0
    for s1 in s:
        dots +=s1.count(".")
    print(dots-c[gy-1][gx-1]-1)

### FIXED CODE ###

H, W = map(int,input().split())
c = [["#"]*(W+2) for _ in range(H+2)]
dots = 0
for y in range(H):
    c[y+1] = "#",*list(input()),"#" 
    dots += c[y+1].count(".")
inf = H*W
m = [[inf]*W for _ in range(H)]
m[0][0] = 0
drs = [[-1,0],[1,0],[0,-1],[0,1]]

s = 0
yx = [[1, 1]]
notgoal = True
while notgoal and yx:
    yx2 = []
    s += 1
    for y,x in yx:
        for dy, dx in drs:
            x2 = x+dx
            y2 = y+dy
            if c[y2][x2] == "." and m[y2-1][x2-1] == inf:
                m[y2-1][x2-1] = s
                if (y2,x2) == (H,W):
                    notgoal = False
                else:
                    yx2.append([y2, x2])
    yx = yx2

if notgoal:
    print("-1")
else:
    print(dots-s-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
a = sorted(list(set(a)))
from fractions import gcd
lc = a[0]
if n != 1:
  for num,i in enumerate(a[1:]):
    if lc == 0:
      break
    lc = lc * i // gcd(lc, i)
    if gcd(lc, i) == min(i,lc):
      for j in a[:num+1]:
        z = i//j
        if z == i/j and z%2 == 0:
          lc = 0
          break 
if lc == 0:
  print(0)
else:
  print((m+lc//2)//lc)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
a = sorted(list(set(a)))
from fractions import gcd
lc = a[0]
if n != 1:
  for num,i in enumerate(a[1:]):
    if lc == 0:
      break
    lc = lc * i // gcd(lc, i)
    if gcd(lc, i) == min(i,lc):
      for j in a[:num+1]:
        if (i/j)%2 == 0:
          lc = 0
          break 
if lc == 0:
  print(0)
else:
  print((m+lc//2)//lc)
### BUGGY CODE ###

import itertools
N = int(input())
S = [int(input()) for _ in range(N)]
cos = [0]
for i in itertools.product([0,1], repeat=N):
  ans = 0
  for j in range(N):
    if i[j] == 1:
      ans += S[j]
  if ans%10 != 0:
    cos.append(ans)
print(max(cos))

### FIXED CODE ###

N = int(input())
S = [int(input()) for _ in range(N)]
if sum(S)%10 != 0:
  print(sum(S))
else:
  A = sorted(S)
  for i in A:
    if (sum(S)-i)%10 != 0:
      print(sum(S)-i)
      exit()
  print(0)
### BUGGY CODE ###

# problem D
mod=10**9+7

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

b=[[0 for i in range(N)] for k in range(60)] # i番目の数の2^kの位(0<=k<60)

for i in range(N):
    for k in range(60):
        b[k][i]=A[i]>>k&1

ans=0
for k in range(60):
    ans+=2**k*b[k].count(0)*b[k].count(1)

print(ans%mod)

### FIXED CODE ###

# problem D
mod=10**9+7

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

b=[[0 for i in range(N)] for k in range(60)] # i番目の数の2^kの位(0<=k<60)
d0=[0 for k in range(60)]
d1=[0 for k in range(60)]

for i in range(N):
    for k in range(60):
        if A[i]>>k&1:
            d1[k]+=1
        else:
            d0[k]+=1

ans2=0
for k in range(60):
    ans2+=2**k*d0[k]*d1[k]

print(ans2%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n,q = map(int,input().split())
tree = {i : [] for i in range(n)}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  tree[b].append(a)
score = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  score[p-1] += x
  
def dfs(parent,node,s):
  s += score[node]
  score[node] = s
  for n in tree[node]:
    if n == parent:
      continue
    dfs(node,n,s)

dfs(-1,0,0)
  
print(' '.join(map(str,score)))
  




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q = map(int,input().split())
tree = {i : [] for i in range(n)}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  tree[b].append(a)
score = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  score[p-1] += x
  
def dfs(parent,node,s):
  for n in tree[node]:
    if n == parent:
      continue
    score[n] += score[node]
    dfs(node,n,s)

dfs(-1,0,0)
  
print(*score)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import collections
n = int(input())
a = [int(i) for i in input().split()]

#累積和を求める
sum_a = [0 for _ in range(n+1)]
for i in range(1, n+1):
    sum_a[i] = sum_a[i-1] + a[i-1]
#print(sum_a)

ans = 0
c = collections.Counter(sum_a)
for i in range(min(sum_a), max(sum_a)+1):
    tmp = c[i]
    if tmp >= 2:
        ans += (tmp * (tmp - 1)) // 2
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
n = int(input())
a = [int(i) for i in input().split()]

#累積和を求める
sum_a = [0 for _ in range(n+1)]
for i in range(1, n+1):
    sum_a[i] = sum_a[i-1] + a[i-1]
#print(sum_a)

ans = 0
c = collections.Counter(sum_a)
for i in set(sum_a):
    tmp = c[i]
    if tmp >= 2:
        ans += (tmp * (tmp - 1)) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 10**6
for i in range(n):
    a, b = s[:i], s[i+1:]
    ans = min(ans, a.count('W') + b.count('E'))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
e_l, e_sum = [], 0
w_l, w_sum = [], 0
for i in range(n):
    if s[i] == 'E':
        e_sum += 1
    else:
        w_sum += 1
    e_l.append(e_sum)
    w_l.append(w_sum)
for i in range(n):
    if i == 0:
        ans = e_l[n-1] - e_l[0]
    elif i == n:
        ans = max(ans, w_l[n-2])
    else:
        ans = min(ans, e_l[n-1] - e_l[i] + w_l[i-1])
print(ans)
### BUGGY CODE ###

N = int(input())
Ss = []
while N > 0:
    s = input()
    if s not in Ss:
        Ss.append(s)
    N = N -1

print(len(Ss))

### FIXED CODE ###

N = int(input())
Ss = set()
while N > 0:
    s = input()
    if s not in Ss:
        Ss.add(s)
    N = N -1

print(len(Ss))
### BUGGY CODE ###

#forループが多重ループになっているせいで時間がかかりすぎる
'''
import itertools
import numpy as np

K = int(input())
result = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            for a, b, c in itertools.combinations([i, j, k], 3):
                result += np.gcd.reduce([a, b, c])
print(result)
'''

import numpy as np

K = int(input())
result = 0

for i in range(1, K+1):
    result += i

for i in range(1, K):
    for j in range(i+1, K+1):
        result += np.gcd(i,j) * 6

if K >= 3:
    for i in range(1, K-1):
        for j in range(i+1, K):
            for k in range(j+1, K+1):
                result += np.gcd.reduce([i,j,k]) * 6

print(result)

### FIXED CODE ###

import math
from math import gcd

K = int(input())
result = 0

for i in range(1, K+1):
    result += i

for i in range(1, K):
    for j in range(i+1, K+1):
        result += gcd(i,j) * 6

if K >= 3:
    for i in range(1, K-1):
        for j in range(i+1, K):
            for k in range(j+1, K+1):
                result += gcd(gcd(i,j),k) * 6

print(result)
### BUGGY CODE ###

n,q=map(int,raw_input().split())
L=[0]*n
for i in range(q):
    a,v=map(int,raw_input().split())
    L[a-1]+=v
    m=max(L)
    print L.index(m)+1,m

### FIXED CODE ###

from collections import defaultdict
n,q=map(int,raw_input().split())
va=defaultdict(set)
av=defaultdict(int)
for i in range(q):
    a,v=map(int,raw_input().split())
    try:
        va[av[a]].remove(a)
        if va[av[a]]==set([]):
            del va[av[a]]
    except KeyError:
        pass
    av[a]+=v
    va[av[a]].add(a)
    m=max(va.keys())
    t=min(va[m])
    print t,m
### BUGGY CODE ###

#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
# DP　使う魔力がk以下 の時の最大攻撃力で漸化式を立てる
# dp[i] = max(dp[i-a[j]]+b[j]) # i-a[j] >= 0となる全てのa[j]に対して
max_magic = b[0]*((h-1)//a[0]+1)
#print(max_magic)
dp = [0]*(max_magic+6)
dp[0] = 0
ans = 0
for i in range(1,max_magic+5):
    dp[i] = dp[i-1] #上書きされない時、それ以下の魔力で与えられた攻撃はいける
    for j in range(n):#すべての種類の魔法に対してループ
        if i -b[j] >= 0:#魔法が使えるなら
            dp[i] = max(dp[i],dp[i-b[j]]+a[j])
    #print(i,dp[i])
    if dp[i] >= h:
        ans = i
        print(ans)
        exit(0)


### FIXED CODE ###

#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
#  dp[i] i 以上の攻撃力を与えるための最小魔力
b,a = zip(*sorted(zip(b,a))) #魔力でソート
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):#すべての種類の魔法に対してループ
        if i -a[j] >= 0:#魔法が使えるなら
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])
### BUGGY CODE ###

h, w, m = map(int, input().split())

h_bomb = [0 for _ in range(h)]
w_bomb = [0 for _ in range(w)]

bomb_xy = {}
for ij in range(m):
    y, x = map(int, input().split())
    h_bomb[y-1] += 1
    w_bomb[x-1] += 1
    bomb_xy[str(y-1)+str(x-1)] = 1

h_max = max(h_bomb)
h_max_index = [i for i, y in enumerate(h_bomb) if y == h_max]

if str(h_max_index[0])+str(0) in bomb_xy:
    ans = h_bomb[h_max_index[0]] + w_bomb[0] - 1
else:
    ans = h_bomb[h_max_index[0]] + w_bomb[0]

# print("ans:", ans)
for j in h_max_index:
    for i in range(w):
        if str(j)+str(i) in bomb_xy:
            temp_max = h_bomb[j] + w_bomb[i] - 1
        else:
            temp_max = h_bomb[j] + w_bomb[i]

        # print("temp:", temp_max)
        if temp_max > ans:
            ans = temp_max

print(ans)


### FIXED CODE ###

import sys

h, w, m = map(int, input().split())

h_bomb = [0 for _ in range(h)]
w_bomb = [0 for _ in range(w)]

bomb_xy = {}
for ij in range(m):
    y, x = map(int, input().split())
    h_bomb[y-1] += 1
    w_bomb[x-1] += 1
    bomb_xy[str(y-1)+str(x-1)] = 1

h_max = max(h_bomb)
h_max_index = [i for i, y in enumerate(h_bomb) if y == h_max]
w_max = max(w_bomb)
w_max_index = [j for j, x in enumerate(w_bomb) if x == w_max]

ans = 0
# print("ans:", ans)
for j in h_max_index:
    for i in w_max_index:
        if str(j)+str(i) in bomb_xy:
            ans = h_bomb[j] + w_bomb[i] - 1
        else:
            print(h_bomb[j] + w_bomb[i])
            sys.exit()

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

N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
for i in range(int(pow(P,1/N))+2,0,-1):
    if P%pow(i,N)==0:
        print(i)
        break

### FIXED CODE ###

from collections import Counter
N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
prime = []
f = 2
while f**2 <=P:
    if P%f==0:
        prime.append(f)
        P//=f
    else:
        f += 1
if P != 1:
    prime.append(f)

ans = 1
for k,v in Counter(prime).items():
    if v//N:
        ans *= k**(v//N)
print(ans)
### BUGGY CODE ###

a, b, k = [int(x) for x in input().split()]
for i in range(k):
    if a!=0:
        a-=1
        k-=1
    else:
        b-=1
        k-=1
print(str(a)+" "+str(b))

### FIXED CODE ###

a, b, k = [int(x) for x in input().split()]
if a<=k:
    k -= a
    a = 0
    if b<=k:
        k -= b
        b = 0
    elif b>k:
        b -= k
        k = 0
else:
    a -= k
    k = 0
print(str(a)+" "+str(b))
### BUGGY CODE ###

n = int(input())
power = 1
for i in range(1,n+1):
    power *= i
print(power % (10**9 + 7))

### FIXED CODE ###

import math
n = int(input())
power = 1
print(math.factorial(n) % (10**9 + 7))
### BUGGY CODE ###

n = input()
n = int(n)
lin = input().split()
# 要素の個数を求める
dic_s = {}
for c in lin:
  dic_s.setdefault(c, 0)
  dic_s[c] += 1
for c in lin:
  tot = 0
  for key,value in dic_s.items():
    v = value
    if key == c:
      v -= 1
    if v > 1:
      tot += v * (v - 1) / 2
  print(int(tot))

### FIXED CODE ###

n = input()
n = int(n)
lin = input().split()
# 要素の個数を求める
dic_s = {}
for c in lin:
  dic_s.setdefault(c, 0)
  dic_s[c] += 1
# ペアの総数
tot = 0
for key,value in dic_s.items():
  v = value
  tot += v * (v - 1) / 2
# print(int(tot))
# 指定位置のペアを除く
for c in lin:
  if tot > 0:
    v = dic_s[c]
    print(int(tot-(v-1)))
  else:
    print(0)
### BUGGY CODE ###

N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)

DP = [[0] * M for _ in range(W + 3)]

for i in range(W+1):
    for j, (weight, value) in enumerate(WEIGHTS):
        if i - weight >= 0:
            DP[i+1][j] = max(x if index != j else 0 for index, x in enumerate(DP[max(i - weight + 1, 0)])) + value

print(max(DP[W + 1]))


### FIXED CODE ###

N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)

DP = [[0 for _ in range(W + 1)] for _ in range(M + 1)]

for i, (weight, value) in enumerate(WEIGHTS):
    for w in range(W + 1):
        if w - weight >= 0:
            DP[i+1][w] = max(DP[i][w - weight] + value, DP[i][w])
        else:
            DP[i+1][w] = DP[i][w]

print(DP[M][W])
### BUGGY CODE ###

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

lst = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            moji1 = lst[i]
            moji2 = lst[j]
            moji3 = lst[k]
            cnt = 0
            kuraberu = [moji1, moji2, moji3]
            for moji in s:
                if moji == kuraberu[cnt]:
                    cnt += 1
                if cnt == 3:
                    ans += 1
                    break

print(ans)

### FIXED CODE ###

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

lst = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            moji1 = lst[i]
            moji2 = lst[j]
            moji3 = lst[k]
            cnt = 0
            kuraberu = [moji1, moji2, moji3]
            for moji in s:
                if moji == kuraberu[cnt]:
                    cnt += 1
                if cnt == 3:
                    ans += 1
                    break

print(ans)