Problem:


Score : 400 points

Problem Statement

We have N balls. The i-th ball has an integer A_i written on it.

For each k=1, 2, ..., N, solve the following problem and print the answer.  

Find the number of ways to choose two distinct balls (disregarding order) from the N-1 balls other than the k-th ball so that the integers written on them are equal.

Constraints

3 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

For each k=1,2,...,N, print a line containing the answer.

Sample Input 1

5
1 1 2 1 2

Sample Output 1

2
2
3
2
3

Consider the case k=1 for example. The numbers written on the remaining balls are 1,2,1,2.

From these balls, there are two ways to choose two distinct balls so that the integers written on them are equal.

Thus, the answer for k=1 is 2.

Sample Input 2

4
1 2 3 4

Sample Output 2

0
0
0
0

No two balls have equal numbers written on them.

Sample Input 3

5
3 3 3 3 3

Sample Output 3

6
6
6
6
6

Any two balls have equal numbers written on them.

Sample Input 4

8
1 2 1 4 2 1 4 1

Sample Output 4

5
7
5
7
7
5
7
5



Sample input:
5
1 1 2 1 2


Sample output:
2
2
3
2
3

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ball = [0] * (n+1)
for i in a:
  ball[i] += 1
base = 0
for i in ball:
  base += i * (i-1) // 2
for i in a:
  b = ball[i]
  ans = base - (b-1) * 2 // 2
  print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

d = Counter(a)

ans = 0

for i, c in d.items():
    ans += d[i] * (d[i] - 1) // 2

for i in a:
    ans_ = ans
    ans_ -= d[i] * (d[i] - 1) // 2
    ans_ += (d[i] - 1) * (d[i] - 2) // 2

    print(ans_)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
d = defaultdict(int)
for a in A:
    d[a] += 1
ans = 0
for v in d.values():
    ans += v*(v-1) //2 

for a in A:
    v = d[a]
    print(ans - (v*(v-1))//2 + ((v-1)*(v-2))//2)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]

    t = Counter(A)
    total = 0
    for k, v in t.items():
        total += v * (v-1) // 2

    for a in A:
        tmp1 = t[a] * (t[a]-1) // 2
        tmp2 = (t[a]-1) * (t[a]-2) // 2
        print(total - tmp1 + tmp2)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = list(map(int, readline().split()))

    cntr = Counter(a)
    tsum = 0

    for key, value in cntr.items():
        temp = (value - 1) * value // 2
        tsum += temp

    for i in range(n):
        k = a[i]
        v = cntr[k]
        print(tsum-(v-1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int,input().split()))
cnt = [0]*200001
for i in a:
    cnt[i] += 1
ans = 0
for i in range(200001):
    if cnt[i] <= 1: continue
    else: 
        ans += cnt[i]*(cnt[i]-1)//2
for i in range(n):
    print(ans-cnt[a[i]]+1)

Submission status: Accepted

Solution code:
import collections
import math
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
zenbu = 0
for i in c.values():
    zenbu += i*(i-1)//2

for i in range(N):
    part = c[A[i]]-1
    print(zenbu-part)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter as cl

def solve(N: int, A: "List[int]"):
    d = cl(A)
    ct = 0
    for x in d.keys():
        ct += d[x] * (d[x] - 1) //2
    for x in A:
        print(ct - (d[x]-1))

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
lst = list(map(int,input().split()))
c = Counter(lst)
res = 0
for k,v in c.items():
    if v >= 2:
        res += v*(v-1)//2
for x in lst:
    if c[x]<2:
        print(res)
    else:
        print(res - (c[x] - 1))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

nums = defaultdict(int)
for a in A:
    nums[a] += 1

total = 0
for k, v in nums.items():
    total += v * (v - 1) // 2

for a in A:
    v = nums[a]
    diff = v * (v - 1) // 2 - (v - 1) * (v - 2) // 2
    print(total - diff)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from collections import Counter

n = int(input())
a = [int(x) for x in input().split()]

c = Counter(a)
# print(c)
total = 0

for i in c.keys():
    # print(c[i])
    if c[i] - 1 > 0:
        total += int((1 / 2) * c[i] * (c[i] - 1))

# print(total)

for i in a:
    ans = total - int((1 / 2) * c[i] * (c[i] - 1))
    if c[i] - 2 > 0:
        ans += int((1 / 2) * (c[i] - 1) * (c[i] - 2))
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    B = [0] * (N + 1)
    for a in A:
        B[a] += 1
    S = 0
    for b in B:
        S += b * (b-1) // 2
    for a in A:
        c = B[a]
        print(S - c*(c-1)//2 + (c-1)*(c-2)//2)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import Counter
ca = Counter(a)

total = 0
for i in ca.values():
    total += i * (i-1) // 2

for i in a:
    diff = ca[i]-1
    print(total - diff)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
d = {}
for i in a:
	if d.get(i, -1) == -1:
		d[i] = 0
	d[i] += 1
s = 0
for i in d:
	s += d[i] * (d[i] - 1) // 2
for i in a:
	print(s - d[i] + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    counts = [0]*N
    combinations = [(0,0)] *N
    ncombinations =[0]*N
    for i in range(N):
        counts[A[i]] += 1
    sum = 0
    for i in range(N):
        c1 = counts[i] * (counts[i]-1)//2 if counts[i] >=2 else 0
        c2 = (counts[i] - 1) * (counts[i] - 2)//2 if counts[i] >= 3 else 0
        combinations[i] = (c1,c2)
        sum += c1
    for i in range(N):
        ncombinations[i] = sum - (combinations[i][0] - combinations[i][1])
    for i in range(N):
        print(ncombinations[A[i]])
    return

def int1(s):
    return int(s)-1
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int1(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = tuple(map(int,input().split()))

c_dic = {}
for i in range(1,n+1):
    c_dic[i] = 0

for i in a:
    c_dic[i] += 1

ans_dic = {}
ans = 0
for i in range(1,n+1):
    ans_dic[i] = (c_dic[i] * (c_dic[i] -1) )//2
    ans += ans_dic[i]

for i in range(n):
    print(ans - max(c_dic[a[i]] -1 , 0))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(n) for n in input().split()]
    dic = [0]*(N+1)
    for a in A:
        dic[a]+=1
    S = 0
    for i in range(1,N+1):
        S += dic[i] * (dic[i]-1) // 2
    for a in A:
        print(S - dic[a] * (dic[a]-1) // 2 + (dic[a]-1) * (dic[a]-2) // 2)
main()

Submission status: Accepted

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

aa = {}
bb = {}
mx = 0
for k,v in d.items():
    aa[k] = v * (v-1) // 2
    bb[k] = (v-1) * (v-2) // 2
    mx += aa[k]

for i in a:
    print(mx - aa[i] + bb[i])

Submission status: Accepted

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

c=Counter(a)
s=0

for i,m in c.items():
    s+=m*(m-1)//2

for i in range(n):
    print(s-c[a[i]]*(c[a[i]]-1)//2+(c[a[i]]-1)*(c[a[i]]-2)//2)

Submission status: Accepted

Solution code:
n=int(input())
d={}
a=list(map(int,input().split()))
for ii in a:
    d[ii]=d.get(ii,0) + 1
ans=0
for i in d:
    ans+=(d[i]*(d[i]-1))//2
for i in a:
    p=(d[i]*(d[i]-1))//2
    q=((d[i]-1)*(d[i]-2))//2
    print(ans -p+q)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    A = list(map(int, input().split()))
    d = defaultdict(int)
    for a in A:
        d[a] += 1

    total = 0
    for i, j in d.items():
        total += (j * (j - 1)) // 2

    for a in A:
        print(total - (d[a] - 1))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
As = list(map(int, input().split()))

ct = Counter(As)
ans = 0
for k, v in ct.items():
    ans += (v * (v-1)) // 2

for a in As:
    c = ct[a]
    if c >= 2:
        print(ans - ((c * (c-1)) // 2) + (((c-1) * (c-2)) // 2))
    else:
        print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int, input().split()))

my_dict = dict()
k_dict = dict()

for i in range(len(a_list)):
    if a_list[i] in my_dict:
        my_dict[a_list[i]] = my_dict[a_list[i]] + 1
    else:
        my_dict[a_list[i]] = 1
    k_dict[i] = a_list[i]

num_c = 0

for item in my_dict:
    num = my_dict[item]
    num_c += ((num * (num - 1)) // 2)

for i in range(n):
    if k_dict[i] in my_dict:
        num = my_dict[k_dict[i]]
        num_1 = num - 1
        print(num_c - ((num * (num - 1)) // 2) + ((num_1 * (num_1 - 1)) // 2))

Submission status: Accepted

Solution code:
n=int(input())
t=[int(i) for i in input().split()]
cnt=[0]*(n+1)
for i in t:
	cnt[i]+=1
	
s = 0
for i in cnt:
	s+=i*(i-1)//2

for i in t:
	g = cnt[i]
	ans = s - g*(g-1)//2 + (g-1)*(g-2)//2
	print(ans)

Submission status: Accepted

Solution code:
import bisect

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

b=sorted(a)

kazu=[]
shurui=[]

gen=0
for i in range(n):
    if(gen!=b[i]):
        kazu.append(1)
        shurui.append(b[i])
        gen=b[i]
    else:
        kazu[-1]+=1


gokei=0
herasi=[]

for k in kazu:
    gokei+=k*(k-1)//2


ans=[]
for i in range(n):
    basho=bisect.bisect_left(shurui,a[i])
    print(gokei-kazu[basho]+1)

Submission status: Accepted

Solution code:
import bisect

n=int(input())
alist = list(map(int, input().split()))
blist=sorted(alist)
clist=[]
dlist=[]
mae=0
for bl in blist:
    if bl==mae:
        clist[-1][1]+=1
    else:
        clist.append([bl, 1])
        dlist.append(bl)
    mae=bl

wa=0
for cl in clist:
    wa+=(cl[1]*(cl[1]-1))//2
for al in alist:
    pos=bisect.bisect_left(dlist, al)
    moto=clist[pos][1]
    if moto==0:
        print(wa)
    else:
        print(wa-moto+1)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))

L=[0]*(max(A)+1)
for i in A:
    L[i]+=1

M=[0]*(len(L))
for i in range(len(L)):
    M[i]=L[i]*(L[i]-1)//2

N=[0]*(len(L))
for i in range(len(L)):
    N[i]=(L[i]-1)*(L[i]-2)//2

S=sum(M)
for i in range(n):
    print(S-M[A[i]]+N[A[i]])

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

L = [0]*(N+1)
for a in A:
    L[a] += 1

ans = 0
for l in L:
    ans += l*(l-1)//2
    
for a in A:
    print(ans - L[a]*(L[a]-1)//2 + (L[a]-1)*(L[a]-2)//2)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
d={}
for i in range(n):
    if a[i] in d:
        d[a[i]]+=1
    else:
        d[a[i]]=1
ans=0
for i in range(n+1):
    if i in d:
        k=d[i]
    else:
        continue
    ans+=k*(k-1)//2
for i in range(n):
    k=d[a[i]]
    ans1=ans
    ans1-=k*(k-1)//2
    ans1+=(k-1)*(k-2)//2
    print(ans1)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
for v in a:
    d[v] += 1

max_ans = 0
for k, v in d.items():
    max_ans += v * (v-1) // 2

ans = []
for v in a:
    if d[v] > 1:
        ans.append(max_ans - ((d[v]) * (d[v]-1) // 2) + ((d[v]-1) * (d[v]-2) // 2))
    else:
        ans.append(max_ans)

print("\n".join(list(map(str, ans))))

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
5
1 1 2 1 2
'''

def solve(l):
	n = len(l)
	d = dict(Counter(l))
	ans = []
	tot = 0
	for i in d:
		j = d[i]
		tot += j*(j-1)//2
	for i in range(n):
		curr = d[l[i]]
		temp = tot - curr + 1
		ans.append(temp)
	return ans


N = int(stdin.readline())
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l)
for i in ans:
	print(i)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
D = {}
for i in A:
  if i in D:
    D[i] += 1
  else:
    D[i] = 1
S = 0
for i in D:
  S += (D[i] * (D[i] - 1)) // 2
for i in range(N):
  print(S - (D[A[i]] - 1))

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
bl = [(i * (i - 1)) // 2 for i in range(N + 3)]
L = [0, 0]
for i in range(1, N + 1):
    L.append(bl[i + 1] - bl[i])
D = defaultdict(int)
for a in A:
    D[a] += 1
RES = 0
for d in D.values():
    RES += bl[d]

for a in A:
    print(RES - L[D[a]])

Submission status: Accepted

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

d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

ans = 0
for a in d:
    n = d[a]
    ans += n * (n-1) // 2

for a in A:
    n = d[a]
    if n >= 2:
        print(ans - n + 1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().strip().split()]
C = defaultdict(int)
for a in A:
    C[a] += 1

sum = 0
for i, c in C.items():
    sum += (c * (c-1)) // 2

for a in A:
    print(sum - (C[a]*(C[a]-1))//2 + ((C[a]-1)*(C[a]-2))//2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import Counter
 
def main():
    N = int(input())
    a = list(map(int,input().split()))
    
    c = [0 for _ in range(max(a))]
    for num in a:
        c[num-1] += 1
    
    count = 0
    for num in c:
        count += (num*(num-1))//2

    for i in a:
        if c[i-1] == 1:
            print(count)
        else:
            num = c[i-1]
            d = (num*(num-1))//2
            p = ((num-1)*(num-2))//2
            print(count-d+p)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
s = [0] * n
ans = 0
for i in range(n):
     s[a[i]-1] +=1
for i in range(n):
     ans += s[i] * (s[i] - 1) // 2
for i in range(n):
     print(ans - (s[a[i]-1]-1) * s[a[i]-1] // 2 +(s[a[i]-1]-1) * (s[a[i]-1] - 2) // 2)

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce

def binom(n, r):
    if n < r or n < 0 or r < 0: return 0
    
    if n - r < r: r = n - r
    if r == 0: return 1
    elif r == 1: return n

    numerator = [n - r + 1 + k for k in range(r)]  # (n-r+1)*(n-r+2)*...*(n-1)*n
    denominator = [1 + k for k in range(r)]         # 1*2*...*(r-1)*r

    # reduce prod(numerator)//prod(denominator)
    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot
    
    # calculate nCr
    return reduce(lambda x, y: x*y, numerator)

N = int(input())
*A, = map(int, input().split())
count = Counter(A)
use_all = {}
use_minus_one = {}
total = 0
for k, v in count.items():
    temp = binom(v, 2)
    total += temp
    use_all[k] = temp
    use_minus_one[k] = binom(v - 1, 2)
for a in A:
    ans = total - use_all[a] + use_minus_one[a]
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
D={}
for i in range(N):
  if A[i] in D:
    D[A[i]]+=1
  else:
    D[A[i]]=1
s=0
for d in D:
  s+=D[d]*(D[d]-1)//2
for i in range(N):
  print(s-D[A[i]]*(D[A[i]]-1)//2+(D[A[i]]-1)*(D[A[i]]-2)//2)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
D={}
for i in range(N):
    if A[i] not in D:
        D[A[i]]=1
    else:
        D[A[i]]+=1
        
MAX=0
for a,b in D.items():
    MAX+=b*(b-1)//2
#print(MAX)

for i in range(N):
    ans=MAX-D[A[i]]*(D[A[i]]-1)//2 + (D[A[i]]-1)*(D[A[i]]-2)//2
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
c=0
for i in range(n):
    b[a[i]-1]+=1
for i in range(n):
    c+=b[i]*(b[i]-1)//2
for i in range(n):
    print(c-b[a[i]-1]+1)

Submission status: Accepted

Solution code:
import sys
from functools import reduce
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res


N = n_in()
A = l_in()

C = [0 for _ in range(N)]

for a in A:
    C[a-1] += 1

res = reduce(lambda memo, c: memo+c*(c-1)//2, C, 0)

for a in A:
    c = C[a-1]
    print(res - c*(c-1)//2 + (c-1)*(c-2)//2)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
count = [0 for i in range(n)]
for i in a:
  count[i-1] += 1
ans = 0
for i in count:
  ans += i*(i-1)//2
for i in a:
  z = count[i-1]
  print(ans-z*(z-1)//2+(z-1)*(z-2)//2)

Submission status: Accepted

Solution code:
from itertools import groupby
import copy

def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2


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

B=copy.copy(A)
s=equalfind(B)
data=groupby(B)
ans=[0 for i in range(0,N+1)]
for key,group in data:
    g=len(list(group))
    ans[key]=g

for i in range(0,N):
    minus=ans[A[i]]-1
    print(s-minus)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
mod = 92709568269121

N = int(input())

def factrial(N):
    fc = [1, 1] + [None] * N
    inv = [0, 1] + [None] * N
    fcInv = [1, 1] + [None] * N
    for i in range(2, N+1):
        fc[i] = i*fc[i-1]%mod
        inv[i] = mod-(inv[mod%i]*(mod//i))%mod
        fcInv[i] = fcInv[i-1]*inv[i]%mod
    return fc, fcInv
fc, fcInv = factrial(N+1)

def modCom(n, k):
    return 0 if n < k else fc[n] * fcInv[k] * fcInv[n-k] % mod

A = [int(x) for x in input().split()]
C = Counter(A)
X = 0
dic1 = defaultdict(int)
dic2 = defaultdict(int)
for x in C.keys():
    dic1[x] = modCom(C[x], 2)
    dic2[x] = modCom(C[x]-1, 2)
    X = X + dic1[x]
for x in A:
    print(X - dic1[x] + dic2[x])

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
from collections import defaultdict

d = defaultdict(int)
for a in As:
    d[a] += 1
cnt = 0
for k in d.keys():
    # print((d[k]-1)*(d[k])//2,"d")
    cnt += (d[k]-1)*(d[k])//2

for a in As:
    x = d[a]
    waru = x*(x-1)//2
    kakeru = (x-1)*(x-2) //2
    print(cnt-waru+kakeru)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
import collections
c=collections.Counter(l)
ans=0
for v in c.values():
    ans+=v*(v-1)//2
for i in l:
    v=c[i]
    print(ans-c[i]+1)

Submission status: Accepted

Solution code:
n = int(input())

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

rec = [0]*(n+1)
for a in ls:
  rec[a] += 1

ans = 0
for a in rec:
  ans += a*(a-1)//2
  
for a in ls:
  print(ans - rec[a] +1)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    *a, = map(int, input().split())

    d = [0] * (N + 1)
    for x in a:
        d[x] += 1

    b = 0
    for x in d:
        b += x * (x - 1) // 2

    for x in a:
        t = b - (d[x] - 1)

        print(t)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
import collections

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

c = collections.Counter(A)

total = sum([ c[n]*(c[n] -1) //2 for n in c])

for k in range(N):
    n = A[k]
    print( total - c[n]*(c[n]-1) // 2 + (c[n] - 1)*(c[n] -2) //2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))
B = [0] * (n+1)
for i in range(n):
    B[A[i]] += 1

C = [0] * (n+1)
for i in range(n+1):
    C[i] = B[i]*(B[i]-1)//2

su = sum(C)

for i in range(n):
    print(su - C[A[i]] + (B[A[i]]-1)*(B[A[i]]-2)//2)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
from collections import Counter
C = Counter(A)

S = 0
for k,v in C.items():
    S += v * (v-1) // 2

for a in A:
    v = C[a]
    print(S-(v-1))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = [0]*N
C = [0]*N
D = [0]*N
for i in range(N):
    B[A[i]-1]+=1
for i in range(N):
    C[i] = int(B[i]*(B[i]-1)/2)
    D[i] = int((B[i]-1)*(B[i]-2)/2)
S = sum(C)
for i in A:
    print(S-C[i-1]+D[i-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

D = defaultdict(int)
for a in A:
    D[a] += 1

ans_base = 0
for v in D.values():
    ans_base += v * (v - 1) // 2

for a in A:
    if D[a] > 1:
        print(ans_base - (D[a] * (D[a] - 1) // 2) + ((D[a] - 1) * (D[a] - 2) // 2))
    else:
        print(ans_base)

Submission status: Accepted

Solution code:
import copy
n=int(input())
a=list(map(int,input().split()))
ans=0
b=copy.copy(a)
a.sort()
cnt=1
num=[0]*n
for i in range(n-1):
	if a[i]==a[i+1]:
		cnt+=1
	else:
		num[a[i]-1]=cnt
		ans+=cnt*(cnt-1)//2
		cnt=1
ans+=cnt*(cnt-1)//2
num[a[-1]-1]+=cnt
for i in range(n):
	x=num[b[i]-1]
	if x<=1:
		print(ans)
	else:
		e=ans-x*(x-1)//2+(x-1)*(x-2)//2
		print(e)

Submission status: Accepted

Solution code:
def comb(n):
    return n * (n-1) // 2


def comb2(n):
    if n == 0:
        return 1
    else:
        return (n-1)*(n-2) // 2


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

count = [0] * N
Comb = 0
for a in A:
    count[a-1] += 1
for i,c in enumerate(count):
    Comb += comb(c)

for a in A:
    c = count[a-1]
    ans = Comb - comb(c) + comb2(c)
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, *A = map(int, open(0).read().split())
ctr = Counter(A)
total = sum(v * (v - 1) // 2 for v in ctr.values())
for v in A:
    c = ctr[v]
    print(total - (c * (c - 1) // 2) + max(0, (c - 1) * (c - 2) // 2))

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
B=[0]*(n+3)
for i in range(n):
  B[A[i]]+=1
ans=0
for i in range(n+3):
  ans=ans+B[i]*(B[i]-1)//2
for i in range(n):
  print(ans-B[A[i]]+1)

Submission status: Accepted

Solution 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
INF = 2**62-1

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):
    c = Counter(A)
    ans = []
    D = {}
    T = 0
    for k, v in c.items():
        D[k] = (((v-1) * (v-2)) // 2, ((v) * (v-1)) // 2)
        T += ((v) * (v-1)) // 2
    for a in A:
        ans.append(T-D[a][1] + D[a][0])
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print('\n'.join(map(str, slv(N, A))))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
ar = list(map(int, input().split()))
cnt = [0 for _ in range(n + 1)]
for a in ar:
    cnt[a] += 1
total = 0
for k in cnt:
    total += k * (k - 1) // 2
for a in ar:
    print(total - cnt[a] + 1)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = {}
for i in a:
    b.setdefault(i, 0)
    b[i] += 1
temp = 0
for i in b.values():
    temp += i * (i - 1) // 2
for i in range(n):
    ans = temp - (b[a[i]] - 1)
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def input():
    return sys.stdin.readline().strip()


N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
ans = 0
for k, v in c.items():
    if v > 1:
        ans += v * (v - 1) // 2

for a in A:
    v = c[a]
    if v > 1:
        print(ans - v * (v - 1) // 2 + (v - 1) * (v - 2) // 2)
    else:
        print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(10**6)

def array2D(row, col ,val=0):
    return [[val]*col for i in range(row)]


def comb2(x):
    if x>=2:
        return x*(x-1)//2
    else:
        return 0

n = int(input())
A = list(map(int, input().split()))
d = {}
for a in A:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1

ans_t = 0
for i in d:
    ans_t += comb2(d[i])

for a in A:
    print(ans_t - comb2(d[a]) + comb2(d[a]-1))

Submission status: Accepted

Solution code:
"""
NTC here
"""
import sys
inp = sys.stdin.readline


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


flush = sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**25)


def iin(): return int(input())


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

# range = xrange
# input = raw_input


def main():
    def fn(n):
        if n<0:return 0
        return (n*(n+1))//2
    n = iin()
    a = lin()
    dc = {}
    for i in a:
        try:
            dc[i]+=1
        except:
            dc[i] = 1
    sm = 0
    for i in dc:
        sm+= fn(dc[i]-1)
    for i in a:
        x = dc[i]
        ch = sm - fn(x-1) + fn(x-2)
        print(ch)

main()
# threading.Thread(target=main).start()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
num = [0 for _ in range(n)]
c = [0 for _ in range(n)]
for i in a:
    num[i - 1] += 1

for i in range(n):
    if num[i] == 0:
        continue
    c[i] = num[i] * (num[i] - 1) // 2
# print(c)
ans = sum(c)
# print(num)
for i in a:
    tmp = (num[i - 1] - 2) * (num[i - 1] - 1) // 2 - num[i - 1] * (num[i - 1] - 1) // 2
    print(ans + tmp, )

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
data = [0] * (N+1)
preans = [0] * (N+1)

for i in range(N):
    data[A[i]] += 1

for i in range(1,N+1):
    preans[i] = (data[i]*(data[i]-1))//2

s = sum(preans)

for i in range(N):
    print(s-data[A[i]]+1)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
balls = {}
for a in A:
  if a in balls:
    balls[a]+=1
  else:
    balls[a] = 1
ans = 0
for a in balls:
  ans += balls[a]*(balls[a]-1)//2

for i in range(n):
  ball = A[i]
  count = balls[ball]
  print(ans - count*(count-1)//2 + (count-1)*(count-2)//2)

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class v:
    def __init__(self, f):
        self.f = f
        self.v = None
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n) 


def main():
    N = int(input())
    A = read_list()
    D = {}
    for a in A:
        D[a] = D.setdefault(a, 0) + 1
    
    S = sum(i * (i - 1) for i in D.values()) // 2
    for k in range(N):
        print(S - (D[A[k]] - 1))


if __name__ == "__main__":
    main()