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())
As = input().split()

dic = {}
for a in As:
  if a not in dic:
    dic[a] = 0
  dic[a] += 1

tmp = 0
for k, v in dic.items():
  if v > 1:
    tmp += v * (v-1)/2

ans = []
for a in As:
  if dic[a] > 1:
    div = dic[a] * (dic[a] - 1) / 2
    kakeru = (dic[a]-1) * (dic[a]-2)/2
    ans.append(int(tmp - div + kakeru))
  else:
    ans.append(int(tmp))
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
def comb(n):
    if (n <= 1):
        return 0
    return (n - 1) * n / 2

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

cnt = [0 for i in range(N + 1)]
for a in A:
    cnt[a] += 1
comb1 = [comb(cnt[a]) for a in A]
comb2 = [comb(cnt[a] - 1) for a in A]

Sum = sum([comb(c) for c in cnt])

for i in range(len(A)):
    print(int(Sum - comb1[i] + comb2[i]))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
from collections import Counter
d=Counter(a)
import math
def cmb(n,r):
    f = math.factorial
    return int(f(n) // f(r) // f(n-r))
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b
e={}
dd=0
for i,j in d.items():
    dd+=combination(j, 2)
    e[i]=combination(j-1, 1)

for i in a:
    print(dd-e[i])

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

memo = defaultdict(lambda: -1)
conv_D = defaultdict(int)
SUM = 0
for d in D:
    conv_D[d] = D[d] * (D[d] - 1) // 2
    SUM += conv_D[d]

for i in range(N):
    if memo[A[i]] == -1:
        tmp = SUM - conv_D[A[i]] + (D[A[i]] - 1)*(D[A[i]] - 2)//2
        print(tmp)
        memo[A[i]] = tmp
    else:
        print(memo[A[i]])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
for a in A:
    d[a] += 1
S = 0
for value in d.values():
    S += value*(value-1)//2
for a in A:
    print(S - (d[a]-1))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
kind=[0]*(2*(10**5)+1) #0はダミー
kind2=[0]*(2*(10**5)+1) #0はダミー
for i in range(n):
    kind[a[i]]+=1
ans=0
for i in range(2*(10**5)+1):
    if kind[i]<=1:
        continue
    num=(kind[i]*(kind[i]-1))//2
    ans+=num
    kind2[i]=(kind[i]*(kind[i]-1))//2
    
for i in range(n):
    b=kind[a[i]]-1
    if b<=1:
        print(ans-kind2[a[i]])
        continue
    num=(b*(b-1))//2
    print(ans-kind2[a[i]]+num)

Submission status: Accepted

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

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

    total = 0
    dp = {}
    dp1 = {}
    for k, v in balls.items():
        u = v * (v - 1) // 2
        if u > 0:
            dp[k] = - u + (v - 2) * (v - 1) // 2
        else:
            dp[k] = 0
        total += u

    for k in A:
        print(total + dp[k])

main()

Submission status: Accepted

Solution code:
kazu = dict()
N=input()
A = [int(i) for i in input().split()]
for a in A:
    if a in kazu:
        kazu[a] += 1
    else:
        kazu[a] = 1

tori = 0
for k in kazu.values():
    tori += k*(k-1)//2
for a in A:
    print(tori - kazu[a]+1)

Submission status: Accepted

Solution code:

import sys
def II(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

N = II()
A = LI()

from collections import Counter
S = Counter(A)
result = sum(list(map(lambda x: int(x*(x-1)/2), S.values())))

for a in A:
	n = S[a]
	print(result-n+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)


def solve(N: int, A: "List[int]"):
    c=[0] * N
    for i in range(N):
        c[A[i]-1] += 1

    kmax=0
    for i in range(N):
        kmax += c[i] * (c[i]-1) // 2

    #print("#",c, kmax)
    for i in range(N):
        toruc = c[A[i]-1]
        if toruc == 0:
            print(kmax)
        else:
            print(kmax-toruc+1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
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())
l = [int(x) for x in input().split()]
num = [0] * N
C = 0
for i in range(N):
  num[l[i] - 1] += 1
for i in range(N):
  C += num[i] * (num[i] - 1) // 2
for i in range(N):
  print(C - num[l[i]-1] + 1)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
minA=min(A)
ans=0
Num=[0 for i in range(maxA-minA+1)]
nC2=[0 for i in range(maxA-minA+1)]
nC21=[0 for i in range(maxA-minA+1)]

for i in A:
    Num[i-minA]+=1

for i in range(maxA-minA+1):
    nC2[i]=(Num[i]*(Num[i]-1))//2
    ans+=nC2[i]
    if Num[i]!=0:
        nC21[i]=((Num[i]-1)*(Num[i]-2))//2

for i in range(N):
    print(ans-nC2[A[i]-minA]+nC21[A[i]-minA])

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
dic=defaultdict(int)
A = list(map(int, input().split()))
for i in range(n):
    dic[A[i]]+=1

tmp=0
for key in dic.keys():
    tmp+=dic[key]*(dic[key]-1)//2

for k in range(n):
    x=dic[A[k]]
    if x>=2:
        ans=tmp-(x*(x-1)//2)+((x-1)*(x-2)//2)
    else: ans=tmp
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
b4 = 100000000
tmp = 0
d = {}
for i in b:
    if(b4!=i):
        d[b4] = tmp
        b4 = i
        tmp = 0
    tmp+=1
d[b4] = tmp
ans = 0

alls = 0
for i in d:
    t = d[i]
    alls += int(t*(t-1)/2)

for i in a:
    t = d[i]
    print(alls - (int(t*(t-1)/2) - int((t-1)*(t-2)/2)))

Submission status: Accepted

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

import collections

c = collections.Counter(a)
total = 0

for i in c:
  if c[i] <=1:
    total += 0
  else:
  	total += c[i]*(c[i]-1)//2
#print(c)
delta = {}
for i in c:
  if c[i]==2:
    delta[i] = 1
  elif c[i]>=3:
    delta[i] = c[i]*(c[i]-1)//2 - (c[i]-1)*(c[i]-2)//2
  else:
    delta[i] = 0

for i in a:
  print(total - delta[i])

Submission status: Accepted

Solution code:
import collections

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

D = collections.defaultdict(int)

for k, v in C.items():
    D[k] += v * (v - 1) // 2

pans = sum(D.values())

for a in A:
    p = (C[a] - 1) * (C[a] - 2) // 2
    ans = pans - D[a] + p

    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math


def combinations_count(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n = int(input())
al = list(map(str, input().split()))
d = defaultdict(lambda: 0)
dd = defaultdict(lambda: 0)
dd_1 = defaultdict(lambda: 0)
for a in al:
    d[a] += 1

sam = 0
for key, value in d.items():
    dd[key] = combinations_count(value, 2)
    dd_1[key] = combinations_count(value-1, 2)
    sam += dd[key]
# print(d)
# print(dd)
# print(sam)
for a in al:
    value = d[a]
    print(sam - dd[a] + dd_1[a])

Submission status: Accepted

Solution code:
from math import factorial
def nc2(n):
	if n<2:
		return 0
	else:
		return (n*(n-1))//2

n = int(input())
arr = list(map(int,input().split()))
d = {}
for i in range(n):
	try:
		d[arr[i]].append(i)
	except KeyError:
		d[arr[i]] = [i]

pick2 = {}
pick1 = {}
for i in d.keys():
	pick2[i] = nc2(len(d[i]))
	pick1[i] = nc2(len(d[i])-1)

sum_pick2 = sum(pick2.values())

done = {}

for i in d.keys():
	done[i] = (sum_pick2 - pick2[i] + pick1[i])

for i in arr:
	print(done[i])

Submission status: Accepted

Solution code:
import collections

n = int(input())
A = list(map(int, input().split()))
Acoun = collections.Counter(A)

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

for i in range(n):
    a = Acoun[A[i]] - 1
    ans = x - (a * (a - 1) // 2 - (a - 1) * (a - 2) // 2)
    print(ans - 1)

Submission status: Accepted

Solution code:
n = int(input())
a= list(map(int, input().split()))
from collections import Counter
c=Counter(a)
dic={}
for k,v in c.items():
    dic[k]=v*(v-1)//2
su=0
for k in dic.values():
    su+=k
for i in a:
    print(su-dic[i]+(c[i]-1)*(c[i]-2)//2)

Submission status: Accepted

Solution code:
import collections

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

counter = collections.Counter(a)

sum_conb = sum([(i*(i-1))/2 for i in counter.values()])

for i in range(n):
  print(int(sum_conb - (counter[a[i]] -1)))

Submission status: Accepted

Solution code:
N = int(input())
arr = list(map(int, input().split()))
cnt = {}
sum_num = 0
for idx in arr:
    if idx in cnt:
        cnt[idx] += 1
    else:
        cnt[idx] = 1

for i in cnt.values():
    sum_num += i * (i - 1) // 2

for idx in arr:
    c = cnt[idx]
    ans = sum_num - c * (c - 1) // 2
    ans = ans + (c - 1) * (c - 2) // 2
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

a_num = defaultdict(int) 
for ak in a:
    a_num[ak] += 1

a_calc = dict()
for k in a_num:
    v = a_num[k]
    a_calc[k] = v * (v -1) // 2

a_sum = 0
for k in a_calc:
    a_sum += a_calc[k]

for k in a:
    v = a_num[k]
    ans = a_sum - a_calc[k] + (v-1)*(v-2) // 2
    print(ans)

Submission status: Accepted

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


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


count = dict()
for i in a:
    if i in count:
        count[i] += 1
    else:
        count[i] = 1
ans = dict()

this = 0
for i, c in count.items():
    this += nc2(c)


for i, c in count.items():
    ans[i] = this - nc2(c) + nc2(c-1)

for x in a:
    print(ans[x])

Submission status: Accepted

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

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

ans = 0
for n in num_list:
    ans += n * (n - 1) // 2

for i in range(N):
    diff = num_list[A[i]] * (num_list[A[i]] - 1) // 2 - (num_list[A[i]] - 1) * (num_list[A[i]] - 2) // 2 if num_list[A[i]] >= 2 else 0
    print(ans - diff)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
dic = collections.Counter(A)
def helper(n):
    return n*(n-1)//2
ans = 0
for i in dic.keys():
    ans += helper(dic[i])
for i in A:
    print(ans-dic[i]+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input().strip())
A = list(map(int, input().split()))

h = {}
for a in A:
  if a not in h:
    h[a] = 0
  h[a] += 1

s = 0
for a, c in h.items():
  if c >= 2:
    s += c * (c-1) // 2

for a in A:
  c = h[a]
  if c == 1:
    print(s)
  else:
    comb = c * (c-1) // 2
    comb_minus = 0
    if c-1 >= 2:
      comb_minus = (c-1) * (c-2) // 2
    print(s - comb + comb_minus)

Submission status: Accepted

Solution code:
N = int(input())
K = list(map(int,input().rstrip().split()))
CK = [0 for i in range(N + 1)]
ans = 0
for i in K:
  CK[i] += 1
for i in range(N + 1):
  ans += CK[i] * (CK[i] - 1) /2
for i in range(N):
  bans = ans - CK[K[i]] * (CK[K[i]] -1 ) / 2 + (CK[K[i]] -1) * (CK[K[i]] -2) / 2
  print(int(bans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
li = [0] * n
cou = [0] * (n+2)
for i in range(n):
    if li[a[i]-1] != 0:
        cou[li[a[i]-1]+1] += 1
    li[a[i]-1] += 1
y = 0
ma = max(li)
for i in range(ma-1):
    k = cou[ma-i] - cou[ma-i+1]
    y += (ma-i) * (ma-i-1) * k // 2
for i in range(n):
    x = li[a[i]-1]
    if x >= 2:
        print(y-x+1)
    else: print(y)

Submission status: Accepted

Solution code:
# n choose 2
def binomial_2(n):
    if n < 2:
        return 0
    else:
        return n * (n - 1) // 2

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

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

tot = 0
for num in dict.values():
    tot += binomial_2(num)

for i in range(N):
    print(tot - dict[A[i]] + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

def main():
    N = ii()
    A = lmis()
    d = {}
    for a in A:
        if a in d:
            d[a] += 1
        else:
            d[a] = 1
    s = sum(v * (v-1) //2 for v in d.values())
    for a in A:
        v = d[a]
        if v <= 1:
            print(s)
        else:
            print(s - (v * (v-1))//2 + ((v-1)*(v-2))//2)


main()

Submission status: Accepted

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


#二項係数(modなし) O(k)
def large_conbination(n,k): #no mod. return nCk.
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
    res2 = 1
    for i in range(1,k+1):
        res2*= i
    return res1//res2
n = int(readline())
lst1 = list(map(int,readline().split()))
c = Counter(lst1)

ans = 0
dic1 = dict()
for i,j in c.items():
    res1 = large_conbination(j,2)
    res2 = large_conbination(j-1,2)
    ans += res1
    dic1[i] = (res1,res2)

for i in lst1:
    res12 = dic1[i]
    print(ans-res12[0]+res12[1])

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
c[a[0]] = c[a[0]]-1
ans = [0]*n
for i,j in c.items():
    ans[i-1] = j*(j-1)//2
d = sum(ans)
print(d)

for k in range(1,n):
    d -= ans[a[k-1]-1]
    d -= ans[a[k]-1]
    c[a[k]] = c[a[k]]-1
    c[a[k-1]] = c[a[k-1]]+1
    x = (c[a[k]]-1)*c[a[k]]//2
    y = (c[a[k-1]]-1)*c[a[k-1]]//2
    ans[a[k]-1] = x
    ans[a[k-1]-1] = y
    d += x+y
    print(d)

Submission status: Accepted

Solution code:
from collections import Counter
from scipy.misc import comb

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

c = Counter(a)
total = 0
for _, i in c.items():
    total += comb(i, 2, exact=True)

for i in a:
    print(total - (c[i]-1))

Submission status: Accepted

Solution code:
def perm(n, r):
    rtn = 1
    for i in range(r):
        rtn *= n-i
    return rtn

def cmb(n, r):
    return perm(n, r) // perm(r, r)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnts = [0]*(2*10**5 + 1)
    for v in a:
        cnts[v] += 1
    buf = 0
    for i in range(2*10**5 + 1):
        if cnts[i] > 0:
            buf += cmb(cnts[i], 2)
    for i in range(n):
        x = a[i]
        if cnts[x] <= 1:
            print(buf)
        else:
            ans = buf
            ans -= cmb(cnts[x], 2)
            print(ans + cmb(cnts[x]-1, 2))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

def cmb(n):
  return n*(n-1)//2

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

#インデックス０は除外
count=[0]*(N+1)
for a in A:
  count[a]+=1

cmbs=[0]*N
for i,c in enumerate(count):
  if i==0:
    continue
  cmbs[i-1]=cmb(c)
SUM=sum(cmbs) 
for i in range(N):
  a=A[i]
  #print(cmbs[a-1])
  ans=SUM-cmbs[a-1]+cmb(count[a]-1)
  print(ans)
  
#print(count, cmbs)

Submission status: Accepted

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 50010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=spf[1] = -1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD

    return (num*(pow(den,MOD-2,MOD)))%MOD

def flush():
    return sys.stdout.flush()

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''

def nc2(n):
    return (n*(n-1))//2

n = int(input())
a = arrIN()
c = Counter(a)
ans = 0
for i in set(a):
    ans+=nc2(c[i])


for i in range(n):
    print(ans-nc2(c[a[i]])+nc2(c[a[i]]-1))

Submission status: Accepted

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

ans = 0
d = defaultdict(int)
for i in A:
    d[i] += 1

for i in range(1, n+1):
    ans += d[i] * (d[i] -1) // 2

for i in A:
    if d[i] <= 1:
        print(ans)
    else:
        print(ans - (d[i] * (d[i] -1)//2) + ((d[i] - 1) * (d[i] - 2) // 2))

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int,input().split()))
aa  = collections.Counter(a)
aakey = list(aa.keys())     
aavalue = list(aa.values())     
ans = 0
for i in range(len(aavalue)):
         ans += (aavalue[i] * (aavalue[i] - 1))//2
for i in range(n):
         val = aa[a[i]]
         print(ans-(val-1))

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 j in d.values():
  ans += j*(j-1)//2
for i in range(n):
  x = d[a[i]]
  print(ans-(x*(x-1)//2)+((x-1)*(x-2)//2))

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
cnt = Counter(a)
s = 0
for v in cnt.values(): s += v*(v-1)//2
for i in range(n): print(s-cnt[a[i]]+1)

Submission status: Accepted

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

count={}
for i in range(len(arr)):
    val=arr[i]
    if val not in count.keys():
        count[val]=1
    else:
        count[val]+=1

big_sum=0
for d in count.keys():
    big_sum+= count[d]*(count[d]-1)/2

for a in arr:
    if a in count.keys():
        if count[a]==1:
            print(int(big_sum))
        else:
            print(int(big_sum-(count[a]-1)))

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import os
import sys
import datetime
from functools import lru_cache
readline=readline = sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s


#@lru_cache(maxsize=None)  
def f():
    return 1
#main
N=int(input())
A=list(map(int,input().split()))
count=[0]*(N+1)
ze=0
for a in A:
    count[a]+=1
for a in count:
    if(a<2):continue
    ze+=(a-1)*a//2

for k in range(1,N+1):
    ans=ze
    num=A[k-1]
    cnt=count[num]
    ans-=(cnt-1)*cnt//2
    ans+=(cnt-2)*(cnt-1)//2
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
freq = [0] * (2 * (10**5) + 5)
for i in l: freq[i] -= -1
count = 0
for i in range(2 * (10**5) + 5):
    if freq[i] >= 2:
        temp = (freq[i] * (freq[i] - 1)) // 2
        count += temp
for i in l:
    if freq[i] == 1: print(count)
    else:
        temp = freq[i] - 1
        if temp == 1: print(count - 1)
        else:
            yoyo = ((freq[i] * (freq[i] - 1)) // 2) - ((temp * (temp - 1)) // 2)
            print(count - yoyo)

Submission status: Accepted

Solution code:
import collections
import sys
from collections import defaultdict

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

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

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

d = defaultdict(list)

for number in c.keys():
    count = c[number]
    d[number] = total - (count-1)

for i in a:
    print(d[i])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
d = {}
for a in A:
    if a not in d:
        d[a] = 0
    d[a] += 1
total = 0
for k, v in d.items():
    if v >= 2:
        total += int(v * (v-1) / 2)

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

Submission status: Accepted

Solution code:

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

num = {}
for i in A:##O(N)
    if i not in num:
        num[i] = 1
    else:
        num[i] += 1


values = list(num.values())
keys = list(num.keys())
S = 0
for i in range(len(keys)):##O(N*2)
    if values[i] >= 2:
        S += values[i]*(values[i]-1)//2

for i in range(N):
    if num[A[i]] >= 3:
        print(S-num[A[i]]*(num[A[i]]-1)//2+(num[A[i]]-1)*(num[A[i]]-2)//2)
    elif num[A[i]] == 2:
        print(S-1)
    else:
        print(S)

Submission status: Accepted

Solution code:
from collections import Counter

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

d = Counter(A)
l = list(d.values())
X = 0
for i in l:
  X += i*(i-1)/2
for i in A:
  x = X
  a = d[i]
  if a != 1:
    x -= a*(a-1)/2
  if a > 1:
    x += (a-1)*(a-2)/2  
  print(int(x))

Submission status: Accepted

Solution code:
N=int(input())
ball=list(map(int,input().split()))
cnt={}
dif={}
for b in ball:
    if b in cnt:
        cnt[b]+=1
    else:
        cnt[b]=1
total=0
for k,cn in cnt.items():
    total+=cn*(cn-1)//2
    dif[k]=(cn-1)*(cn-2)//2-cn*(cn-1)//2
for b in ball:
    print(total+dif[b])

Submission status: Accepted

Solution code:
from collections import Counter

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

cnt = Counter(A)

cmb = 0
for a, c in cnt.items():
    if c >= 2:
        cmb += c * (c - 1) // 2

for a in A:
    minus = 0 if cnt[a] < 2 else cnt[a] * (cnt[a]-1) // 2
    c = cnt[a] - 1
    plus = 0 if c < 2 else c * (c-1) // 2
    ans = cmb - minus + plus
    print(ans)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int,input().split()))
x = collections.Counter(a)
keys = []
values = []
b = list(set(a))
for i in b:
    z = x[i]
    keys.append(i)
    values.append(z*(z-1)//2)
s = sum(values)
d = dict(zip(keys,values))
for i in a:
    ans = s
    ans -= d[i]
    ans += (x[i]-1)*(x[i]-2)//2
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 19 20:52:57 2020

@author: over-
"""

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

D=dict()

for a in A:
    if a not in D:
        D[a]=1
    else:
        D[a]+=1

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

for a in A:
    d=D[a]
    if d!=1: 
        add=(d-1)*(d-2)/2-d*(d-1)/2
    else:
        add=0
    print(int(ans+add))

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = list(map(int, input().split()))
r = {}
for i in range(N):
    if A[i] in r:
        r[A[i]]+=1
    else:
        r.setdefault(A[i], 1)
total = 0
for k, v in r.items():
    if v>=2:
        total += v*(v-1)//2
for k in range(N):
    num = r[A[k]]
    print(total - (num-1))

Submission status: Accepted

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

hs = dict()
for i in range(len(a)):
    hs[a[i]] = hs.get(a[i], 0) + 1

pattern = 0
for k in hs:
    if hs[k] <= 1:
        continue
    pattern += hs[k] * (hs[k] - 1) // 2

for i in range(len(a)):
    if hs[a[i]] <= 1:
        print(pattern)
    else:
        print(pattern - (hs[a[i]] * (hs[a[i]] - 1) // 2) + ((hs[a[i]] - 1) * (hs[a[i]] - 2) // 2))

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = [int(s) for s in input().split()]
C = Counter(A)

max_value = 0
for c, cnt in C.items():
    max_value += cnt * (cnt - 1) // 2 if cnt >= 2 else 0

for a in A:
    n = C[a]
    if n >= 2:
        print(max_value - (n * (n - 1) // 2 - (n - 1) * (n - 2) // 2))
    else:
        print(max_value)

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def Nc2(n):
    return n * (n - 1) // 2


N = int(input())
A = list(map(int, input().split()))
AA = sorted(A)
num = [0] * (N + 10)
num2 = [0] * (N + 10)
val = 0
for i in range(N - 1):
    if AA[i] == AA[i + 1]:
        val += 1
    else:
        val += 1
        num[AA[i]] = Nc2(val)
        num2[AA[i]] = val
        val = 0
    if i == N - 2:
        val += 1
        num[AA[i + 1]] = Nc2(val)
        num2[AA[i + 1]] = val
summ = sum(num)
for i in range(N):
    print(summ - num[A[i]] + Nc2(num2[A[i]] - 1))

Submission status: Accepted

Solution code:
N = int(input())

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

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

dic2 = {}
sum_ = 0
for key, val in dic.items():
    if val < 2:
        dic2[key] = (0, 0)
    elif val == 2:
        dic2[key] = (1, 0)
        sum_ += 1
    else:
        x = int((val * (val - 1)) / 2)
        val -= 1
        y = int((val * (val - 1)) / 2)

        dic2[key] = (x, y)
        sum_ += x

for k in range(N):
    t = A[k]

    print(sum_ - dic2[t][0] + dic2[t][1])