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:
import collections
MOD = 10**18+9
n = int(input())
a = list(map(int, input().split()))
b = [[0 for j in range(2)] for i in range(n)]
c = collections.Counter(a)
s = 0
def nCr(nn, r, mod):
	r = min(r, nn-r)
	numer = denom = 1
	for i in range(1, r+1):
		numer = numer * (nn+1-i) % mod
		denom = denom * i % mod
	return numer * pow(denom, mod-2, mod) % mod
for i in c:
	if c[i] < 2:
		b[i-1][0] = 0
	else:
		b[i-1][0] = nCr(c[i],2,MOD)
		s += b[i-1][0]
	if c[i]-1 < 2:
		b[i-1][1] = 0
	else:
		b[i-1][1] = nCr(c[i]-1,2,MOD)
for i in a:
	ans = s-b[i-1][0] + b[i-1][1]
	print (ans)

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n = int(input())
  a = [int(i) for i in input().split()]
  Ss = set(a)
  s = list(Ss)
  import collections
  c = collections.Counter(a)
  j = 0
  #print(c[a[0]])
  for i in range(len(s)):
    j += int(c[s[i]]*(c[s[i]]-1)/2)
  #print(j)
  for i in range(n):
    if c[a[i]] >= 2:
      print(int(j-(c[a[i]]-1)))
    else:
      print(j)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split(' ')))
import math
import collections
import operator as op
from functools import reduce
def nCr(n,r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom if n>1 else 0
counter=collections.Counter(A)
penult=0
for i in range(1,N+1):
    penult=penult+nCr(counter[i],2)
for i in range(0,N):
    print(int(penult-(counter[A[i]]-1)))

Submission status: Accepted

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

C = collections.Counter(L)
ans = 0
for i in C.items():
    ans += int((i[1]*(i[1]-1))/2)
        
for i in range(N):
    del_target = L[i]
    print(ans - (C[del_target]-1))

Submission status: Accepted

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

number_count = {}
for cmp in data:
    if cmp in number_count:
        number_count[cmp] += 1
        continue
    number_count[cmp] = 1

C_tot = 0
for cmp in number_count:
    C_tot += int(number_count[cmp] * (number_count[cmp] - 1) / 2)

for k in range(N):
    C = C_tot - int(number_count[data[k]] * (number_count[data[k]] - 1) / 2) + int((number_count[data[k]] - 1) * (number_count[data[k]] - 2) / 2)
    print(str(C))

Submission status: Accepted

Solution code:
import collections

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

ans=0
ll=[0]*(n+1)
for i in l:
    ans-=int(ll[i]*(ll[i]-1)/2)
    ll[i]+=1
    ans+=int(ll[i]*(ll[i]-1)/2)
#print(ll)
for j in l:
    b=int(ll[j]*(ll[j]-1)/2)
    c=int((ll[j]-1)*(ll[j]-2)/2)
    print(ans-b+c)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
box = list(map(int, input().split()))
c = defaultdict(int)
for b in box:
    c[b] += 1
    
anss = sum([int(1/2 * c[k] * (c[k] - 1)) for k in c.keys()])
for b in box:
    fi = anss - int(1/2 * c[b] * (c[b] - 1)) + int(1/2 * (c[b]-1) * (c[b] - 2)) 
    print(fi)

Submission status: Accepted

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

values = {}
for i in nums:
  if i in values: values[i] += 1
  else: values[i] = 1

sums={} # 各値ごとの組み合わせ数
subsums={} # 各値ごとの組み合わせ数（ボールがないとき版
allsum = 0
for k,v in values.items():
  sums[k] = v * (v - 1) / 2
  undersum = (v - 2) * (v - 1) / 2 if v > 1 else 0
  subsums[k] = sums[k] - undersum
  allsum += sums[k]

# res={} # 各値のない時版 + 他の合計
# for k,v in sums.items():

for i in nums:
  print(int(allsum - subsums[i]))

Submission status: Accepted

Solution code:
# 2020/03/22
# AtCoder Beginner Contest 159 - D

# Input
n = int(input())
a = list(map(int,input().split()))
acntl = [0] * (n + 1)
anl = [0] * (n + 1)

# Count
for i in range(n):
    acntl[a[i]] = acntl[a[i]] + 1

# Calc Combination
for i in range(n + 1):
    anl[i] = acntl[i] * (acntl[i] - 1) // 2
    anl[0] = anl[0] + anl[i]

# Output
for i in range(n):
    ans = anl[0] - anl[a[i]] + ((acntl[a[i]] - 1) * max(0, acntl[a[i]] - 2)) // 2
    print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import Counter

n = int(sys.stdin.readline())
a = sys.stdin.readline().split()
c = Counter(a)

total_comb_num = sum(map(lambda v: max(v*(v-1)//2, 0), c.values()))
for num in a:
    x = c[num]
    print(total_comb_num + max((x-1)*(x-2)//2, 0) - max((x*(x-1)//2, 0)))

Submission status: Accepted

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

Submission status: Accepted

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

import collections
c = collections.Counter(A)
B=list(c.values())
ans=0
for k in range(len(B)):
    ans+=B[k]*(B[k]-1)/2
for i in range(N):
  anser=ans
  anser=anser+1-c[A[i]]
  print(int(anser))

Submission status: Accepted

Solution code:
from collections import Counter
import math

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

    cnt = Counter(A)
    # print(cnt)
    def comb(n, r):
        if n - r < 0: return 0
        if n - r < r: r = n - r
        if r == 0: return 1
        if r == 1: return n

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

        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

        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])

        return result
    cnt_comb = {}
    sm = 0
    for key, val in cnt.items():
        tmp = comb(val, 2)
        cnt_comb[key] = tmp
        sm = sm + tmp
    # print(cnt_comb)

    # print(list(A))
    for a in A:
        comb_val = cnt_comb.get(a)
        cmb = comb(cnt.get(a) - 1, 2)
        print(sm - comb_val + cmb)



if __name__ == '__main__':
    solver()

Submission status: Accepted

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

Submission status: Accepted

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

# define combination
combs = [0, 0]
for i in range(2, N+1):
    combs.append(i*(i-1)//2)

# process
nums = [0]*(N+1)
for a in A:
    nums[a] += 1

sumall = 0
for n in nums:
    sumall += combs[n]

ans = [sumall]*N
for i, a in enumerate(A):
    n = nums[a]
    ans[i] += combs[n-1] - combs[n]

# output
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
sum = 0

d = {}
d_sum = {}
dd_sum = {}

for aa in a:
    if aa not in d:
        d[aa] = 0
    d[aa] += 1

for dd in d.keys():
    sum += d[dd] * (d[dd]-1) // 2
    d_sum[dd] = d[dd] * (d[dd]-1) // 2

for i in range(len(a)):
    buf = a[i]
    tmp = sum
    tmp -= d_sum[buf]
    tmp += (d[buf] - 1) * (d[buf] - 2) // 2
    print(tmp)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]

num = [0]*n

for i in a:
    num[i-1] += 1


tmp=0
for i in num:
    if i>=2:
        tmp+=(i*(i-1))//2

for i in a:
    if num[i-1]>=2:
        print(tmp-(num[i-1]-1))
    else:
        print(tmp)

Submission status: Accepted

Solution code:
from collections import defaultdict

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split(" ")))

    variation = set(a)
    a_count_dict = defaultdict(int)
    for j in a:
        a_count_dict[j] += 1

    total = 0
    c_dict = {}
    for i in variation:
        count = a_count_dict[i]
        if count > 1: # 2個以上
            # c = combinations_count(count, 2)
            c = count * (count - 1) // 2
        else:
            c = 0
        c_dict[i] = c
        total = total + c

    # total = 0
    # c_list = []
    # a_count_list = []
    # for i in range(n):
    #     count = a.count(i + 1)
    #     a_count_list.append(count)
    #     # print(count)
    #     if count > 1: # 2個以上
    #         # c = combinations_count(count, 2)
    #         c = count * (count - 1) // 2
    #     else:
    #         c = 0
    #
    #     c_list.append(c)
    #     total = total + c

    # print(a, c_list, total, a_count_list)
    for k in range(n):
        ck = c_dict[a[k]]
        ca = a_count_dict[a[k]]
        if ck == 1 or ck == 0:
            q = ck
        else:
            # q = c_list[a[k] - 1] - 1
            q = ck - ck * (ca - 2) // ca


        # if c_list[a[k] - 1] == 1:
        #     q = 1
        # elif c_list[a[k] - 1] == 0:
        #     q = 0
        # else:
        #     # q = c_list[a[k] - 1] - 1
        #     q = c_list[a[k] - 1] - c_list[a[k] - 1] * (a_count_list[a[k] - 1] - 2) // a_count_list[a[k] - 1]
        print(total - q)

Submission status: Accepted

Solution code:
import math
import collections


def C(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input().split()[0])
a_list = list(map(int, input().split()))

counter = collections.Counter(a_list)
ans_dict_1 = {}
ans_dict_2 = {}

for k, v in counter.items():
    if v >= 2:
        ans_dict_1[k] = C(v, 2)
    if v >= 3:
        ans_dict_2[k] = C(v - 1, 2)
total_w = sum(ans_dict_1.values())

for k in range(N):
    n = a_list[k]

    if counter[n] >= 3:
        w = total_w - ans_dict_1[n] + ans_dict_2[n]
    elif counter[n] >= 2:
        w = total_w - ans_dict_1[n]
    else:
        w = total_w
    print(w)

Submission status: Accepted

Solution code:
from collections import Counter as C
n = int(input())
a = list(map(int,input().split()))
d = C(a)
res = 0
for i in d.keys():
	res+=d[i]*(d[i] - 1) // 2
ans = res
for k in range(n):
	yy = d[a[k]] - 1
	res+= (yy * (yy - 1) // 2)
	res-= (d[a[k]] * (d[a[k]] - 1) // 2)
	print(res)
	res = ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

        ans.append(sum)

    return ans

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

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:
n = int(input())
a = list(map(int, input().split()))

import copy

from collections import Counter


ans = [0] * n
b = Counter(a)
sm = 0
for i,j in b.items():
    if j >= 2:
        sm += j*(j-1)//2

for i in range(n):
    ans[i] = sm - b[a[i]] + 1
print(*ans)

Submission status: Accepted

Solution code:
import collections

n = int(input())
A = list(map(int, input().split(' ')))
 
c = dict(collections.Counter(A))
num_dict = {}
total = 0
for a, count in c.items():
  num_dict[a] = (count*(count-1)/2, (count-1)*(count-2)/2)
  total += count*(count-1)/2

ans_dict = {}
for a in c.keys():
  ans_dict[a] = total - num_dict[a][0] + num_dict[a][1]

for k in range(n):
  print(int(ans_dict[A[k]]))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
num = [0]*n
for i in A:
  num[i-1] += 1
def comb(n):
    if n < 2:
      return 0
    else:
      return n * (n-1) // 2
ans_sub = 0
for i in num:
  ans_sub += comb(i)
for i in A:
  if num[i-1] < 2:
    a = 0
  else:
    a = num[i-1]-1
  print(ans_sub-a)

Submission status: Accepted

Solution code:
def f(n):#nC2の関数
    if n==0:
        return 0
    return n*(n-1)/2
N=int(input())
A=list(map(int,input().split()))
d=dict()
e=dict()
ans=0
for i in range(N):#辞書を作る
    if A[i] not in d:
        d[A[i]]=0
    d[A[i]]+=1

for j in d:#それぞれのキーの個数をnC2として保存
    e[j]=f(d[j])
    ans+=e[j]#nC2の総和をとる

for i in A:
    print(int(ans-d[i]+1))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
amax=max(a)+1

s=[0]*amax
for ii in range(n):
    s[a[ii]]=s[a[ii]]+1

ss=0
for ii in range(amax):
    ss=ss+((s[ii]-1)*s[ii])//2

for ii in range(n):
    if s[a[ii]]==0:
        print(ss)
    else:
        sai=s[a[ii]]
        t=ss-(sai*(sai-1))//2+((sai-1)*(sai-2))//2
        print(t)

Submission status: Accepted

Solution code:
N = int(input())
import copy
import math
def nP2(N):
    return (math.factorial(N)/((math.factorial(2))*math.factorial(N-2)))
L = list(map(int,input().split()))
Count = [0 for _ in range(N+1)]
for el in L:
    Count[el]+=1
res = 1
for i in Count:
    if i>=2:
        res += nP2(i)
for balls in L:
    print(int(res-Count[balls]))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(v) for v in input().split()]
    C = [0] * (N + 1)

    for i in A:
        C[i] += 1

    b = 0
    
    for cnt in C:
        b += ((cnt * (cnt - 1)) // 2)

    for i in range(N):
        p = ((C[A[i]] - 1) * (C[A[i]] - 2)) >> 1
        m = (C[A[i]] * (C[A[i]] - 1)) >> 1
        print(b - m + p)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-03-22 21:55:41 +0900
# LastModified: 2020-03-22 22:18:26 +0900
#


import os
import sys
from collections import Counter as ct

def main():
    N = int(input())
    A = list(map(int,input().split()))
#    print(A)
    c = ct(A)
#    print(c)
    d = {}
    total = 0
    for key in c:
        d[key] = c[key]*(c[key]-1)//2
        total += d[key]
#    print(d)
#    print(total)
    for a in A:
        print(total-c[a]+1)

        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin

N = int(input())
readline = stdin.readline
A = list(readline().split())

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

dmemo = {}
for a in A:
    dmemo.setdefault(a, 0)
    dmemo[a] += 1

max_num = 0
cmemo = {}
for dk, dv in dmemo.items():
    if dv not in cmemo:
        val = ncr(dv)
        cmemo[dv] = val
    max_num += cmemo[dv]

for a in A:
    val = dmemo[a]
    a1 = ncr(val)
    a2 = ncr(val-1)
    ans = max_num - a1 + a2
    print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
def cmb(n,r):
  if n<r:
    return 0
  r = min(n-r,r)
  if r == 0: return 1
  over = reduce(mul, range(n, n - r, -1))
  under = reduce(mul, range(1,r + 1))
  return over // under
from collections import Counter as cnt
n=int(input())
l=list(map(int,input().split()))

dic=cnt(l)

s1={}
s2={}
for k,v in dic.items():
  s1[k]=cmb(v,2)
  s2[k]=cmb(v-1,2)
s=sum(s1.values())
for i in range(n):
  x=l[i]
  print(s-s1[x]+s2[x])

Submission status: Accepted

Solution code:
import collections

N = int(input())
k = input().split(" ")
m = {}

#print(k)

c = collections.Counter(k)
#print(c)

for i in c:
    m[i] = c[i]*(c[i]-1)//2        
total = sum(m.values())
#print(m)
#print(total)


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

Submission status: Accepted

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

import collections
c = collections.Counter(a_list)

dict_items = list(c.items())

ans_max = 0
for j in range(len(dict_items)):
    ans_max += ((dict_items[j][1] - 0) * (dict_items[j][1] - 1)) / 2
    
for i in range(n): # kごと
    tmp = c[a_list[i]]
    ans_tmp = ans_max - tmp*(tmp-1)/2 + (tmp-1)*(tmp-2)/2
    print(int(ans_tmp))

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import numpy as np

n = ii()
a = li()

def cmb(n, r):
    if n - r < r: r = n - r
    if n == 0: return 0
    if n == 1: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    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
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result


memo_cnt = [0]*n
memo_cmb = [0]*(n+1)
memo_cmb2 = [0]*(n+1)

for i in range(n):
    memo_cnt[a[i]-1] += 1

for k,i in enumerate(memo_cnt):
    if i >= 3:
        memo_cmb[k+1] = cmb(i,2)
        memo_cmb2[k+1] = cmb(i-1,2)
    elif i == 2:
        memo_cmb[k+1] = cmb(i,2)

cmb_cumsum = np.array(memo_cmb).cumsum()

# print('cumsum')
# print(memo_cnt)
# print(memo_cmb)
# print(cmb_cumsum)

for i in range(n):
    a_now = a[i]
    itself = memo_cmb2[a_now]
    
    other = cmb_cumsum[a_now-1] + cmb_cumsum[-1] - cmb_cumsum[a_now]

    print(itself + other)

Submission status: Accepted

Solution code:
def cycle(x):
    result = 0
    for y in range(int(x), 0, -1):
        result += y - 1
    return result


def main():
    input()
    a_list = list(map(int, input().split(' ')))
    dict_a_list = dict()
    dict_result = dict()
    for a in a_list:
        if a in dict_a_list:
            dict_a_list[a] += 1
            continue
        dict_a_list[a] = 1
    for a in a_list:
        result = 0
        if dict_a_list[a] in dict_result:
            print(dict_result[dict_a_list[a]])
            continue
        dict_a_list[a] -= 1
        for v in dict_a_list.values():
            result += cycle(v)
        print(result)
        dict_a_list[a] += 1
        dict_result[dict_a_list[a]] = result


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import os
import time
import collections
from collections import Counter, deque
import itertools
import math
import timeit
import random
from io import BytesIO, IOBase
 
#########################
# imgur.com/Pkt7iIf.png #
#########################
 
def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r
 
def divs(n, start=1):
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors
 
def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t
 
def flin(d, x, default=-1):
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return (default, default)
    else:
        return (left, right)
 
def ceil(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def prr(a, sep=' '): print(sep.join(map(str, a)))
def dd(): return collections.defaultdict(int)
def ddl(): return collections.defaultdict(list)
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
	newlines = 0
 
	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = "x" in file.mode or "r" not in file.mode
		self.write = self.buffer.write if self.writable else None
 
	def read(self):
			while True:
					b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
					if not b:
							break
					ptr = self.buffer.tell()
					self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
			self.newlines = 0
			return self.buffer.read()
 
	def readline(self):
			while self.newlines == 0:
					b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
					self.newlines = b.count(b"\n") + (not b)
					ptr = self.buffer.tell()
					self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
			self.newlines -= 1
			return self.buffer.readline()
 
	def flush(self):
			if self.writable:
					os.write(self._fd, self.buffer.getvalue())
					self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
	def __init__(self, file):
			self.buffer = FastIO(file)
			self.flush = self.buffer.flush
			self.writable = self.buffer.writable
			self.write = lambda s: self.buffer.write(s.encode("ascii"))
			self.read = lambda: self.buffer.read().decode("ascii")
			self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
'''for _ in range(ii()):
    n=ii()
    a=li()
    m,k,md=0,0,0
    mn,mx=10**9+1,-10**9-1
    for i in range(n-1):
        if a[i]!=-1 and a[i+1]!=-1:
            m=max(m,abs(a[i]-a[i+1]))
    for i in range(1,n-1):
        if a[i]==-1:
            if a[i+1]!=-1:
                mn=min(mn,a[i+1])
                mx=max(mx,a[i+1])
            if a[i-1]!=-1:
                mn=min(mn,a[i-1])
                mx=max(mx,a[i-1])
    if mn==10**9+1 and mx==-10**9-1:
        print(0,0,sep=' ')
    else:
        md=(mn+mx+1)//2
        m=max(abs(mx-md),abs(mn-md),m)
        print(m,md,sep=' ')'''

'''for _ in range(ii()):
    n,m=mi()
    tg=n//2
    n0=n-m
    total=(n*(n+1))//2
    res=0
    if n0<n:
        if m>=tg:
            res=total-n0
        else:
            i=tg-m
            if n&1:
                nn0=2*i+1
            else:
                nn0=2*i
            res=total-((nn0*(nn0+1))//2)-(n0-nn0)
            #print(nn0,n0-nn0)
    print(res)'''
#***************************************************************************************************************************


'''def solve():
    n=int(input())
    a=list(map(int,input().split()))
    diff=len(set(a))
    if diff==1: print (int((n*(n+1))/2))
    elif diff==n: print (1)
    else:
        i=j=ans=0
        ahead=True
        distinct={}
        while j<n:
            if ahead:
                distinct[a[j]]=distinct[a[j]]+1 if a[j] in distinct else 1
                if len(distinct)==diff:
                    ahead=False
                else:
                    j+=1
            else:
                ans+=n-j
                if distinct[a[i]]>1:
                    distinct[a[i]]-=1
                else:
                    distinct.pop(a[i])
                    j+=1
                    ahead=True
                i+=1
        print (ans)
 
solve()'''

#******************************************************************************************

'''s=input()
n=len(s)
i,cntl,cntg=0,0,0
res,fl,fg=0,0,0
while(i<n):
    if s[i]=='<':
        while(i<n and s[i]!='>'):
            fl=1
            cntl+=1
            i+=1
    else:
        while(i<n and s[i]!='<'):
            fg=1
            cntg+=1
            i+=1
    if fl==1 and fg==1:
        res+=max(cntl,cntg)
        cntl-=1
        cntg-=1
        res+=cntl*(cntl+1)//2
        res+=cntg*(cntg+1)//2
        fl,fg,cntl,cntg=0,0,0,0
if fl:
    res+=cntl*(cntl+1)//2
if fg:
    res+=cntg*(cntg+1)//2
print(res)'''


#********************************************************************************************************

def nc2(n):
    return (n*(n-1))//2
n=ii()
a=li()
d=dd()
for i in range(n):
    d[a[i]]+=1
res=0
for k in d:
    res+=nc2(d[k])
for i in range(n):
    print(res-d[a[i]]+1)

Submission status: Accepted

Solution code:
import sys
from math import sqrt
from collections import Counter

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    _ = I()
    a_list = input().split()

    c = Counter(a_list)
    n = {}
    t = 0
    for k, v in c.items():
        n[k] = v - 1
        if v >= 2:
            t += int(v * (v - 1) / 2)

    for a in a_list:
        print(t - n[a])
    pass


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
l =  input()
s= l.split(" ")
for i in range(len(s)):
    s[i] = int(s[i])
v = dict()
sumi = 0
for i in s:
    if not i in v:
        v[i] = 1
    else:
        v[i]+=1
for i in v:
    if v[i]>=2:
        sumi+=v[i]*(v[i]-1)/2
for i in s:
    if v[i]>=2:

        if v[i]==2:
            print(int(sumi-1))
        else:
            print(int(sumi-v[i]*(v[i]-1)/2+(v[i]-2)*(v[i]-1)/2))
    else:
        print(int(sumi))

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

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


for i in range(n):
    b = d[a[i]]
    print(count-b+1)

Submission status: Accepted

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

num_count = {}
count_comb = {}
num_ans = {}
sum_combs = 0

def comb2(n):
    if n not in count_comb:
        count_comb[n] = (n * (n - 1)) // 2
    return count_comb[n]

def ans(ex_num):
    ex_count = num_count[ex_num]
    return sum_combs + comb2(ex_count - 1) - comb2(ex_count)
    # if ex_num in num_ans:
    #     return num_ans[ex_num]

    # result = 0
    # for n, c in num_count.items():
    #     if n == ex_num:
    #         result += comb2(c - 1)
    #     else:
    #         result += comb2(c)
    # num_ans[ex_num] = result
    # return result


for a in As:
    if a not in num_count:
        num_count[a] = 0
    num_count[a] += 1

for _, c in num_count.items():
    sum_combs += comb2(c)

for a in As:
    print(ans(a))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = {}
c = {}
for i in range(n):
  try:
    l[a[i]] += 1
  except:
    l[a[i]] = 1

for k,v in l.items():
  c[k] = v*(v-1)/2

sum_val = sum(c.values())

for j in a:
  v = l[j] - 1
  print(int(sum_val - c[j] + v*(v-1)/2))

Submission status: Accepted

Solution code:
import collections
import numpy as np
from math import factorial

N = int(input())

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

cntr = collections.Counter(A)

uni_A = np.unique(A)

def comb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

comb_d = dict()

for a in uni_A:
    n = cntr[a]
    comb_d[a] = comb(n, 2) if n > 1 else 0

d = dict()
S = sum(comb_d.values())
for a in uni_A:
    s = S - (cntr[a] - 1)
    d.update({a:s})

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

Submission status: Accepted

Solution code:


#####

import numpy as np
# from numpy import int64, int8
from collections import Counter

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
# import sys
# sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def unique(x):
	count=Counter()
	for xi in x:
		count[xi]+=1
	u,c=zip(*count.items())
	return u,c



def main(inputs):
	n=int(inputs[0][0])
	aa=getIntList(inputs[1])

# 	n=200000
# 	aa=np.random.randint(1,n+1,n)
	
# 	print("start")
# 	aa=np.array(aa)
# 	aUnique, count=np.unique(aa, return_counts=True)

	aUnique, count=unique(aa)
	aUnique=np.array(aUnique, np.int64)
	count=np.array(count, np.int64)
	
# 	print(n)
# 	print("aa",aa)
# 	print("aUnique",aUnique)
# 	print("count  ",count)
	
# 	countUnique,countCount=np.unique(count, return_counts=True)
	countUnique,countCount=unique(count)
	countCount=np.array(countCount, np.int64)
	
	pat={}
	countAns=np.empty(len(countUnique), np.int64)
	countAns1=np.empty(len(countUnique), np.int64)
	for ci,c in enumerate(countUnique):
		if c not in pat:
			ni=c*(c-1)//2
			pat[c]=ni
		countAns[ci]=pat[c]
		
		c-=1
		if c not in pat:
			ni=c*(c-1)//2
			pat[c]=ni
		countAns1[ci]=pat[c]
	
# 	print("countUnique",countUnique)
# 	print("countCount ",countCount)
# 	print("countAns ",countAns)
# 	print("countAns1",countAns1)
	
	countUniqueIndex=dict([(c,i) for i,c in enumerate(countUnique)])
# 	print("countUniqueIndex", countUniqueIndex)
	
# 	uniNums=np.empty(len(aUnique), np.int64)
	nums=np.empty(n, np.int64)
	ans={}
	for cui,cu in enumerate(countUnique):
		countCount[cui]-=1
		num0=(countAns*countCount).sum()
		countCount[cui]+=1
		num1=countAns1[cui]
		num=num0+num1
# 		print(cu,num)
		countMask=count==cu
# 		uniNums[countMask]=num
		targetA=aUnique[countMask]
# 		print(targetA)
		for a in targetA:
			ans[a]=num
# 		print(targetA[None,:])
# 		print(aa[:,None])
# 		aMask=(aa[:,None]==targetA[None,:]).any(axis=1)
# 		print(aMask)

# 		nums[aMask]=num
# 	print("\n".join(map(str,nums)))

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

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
b=[x for x in a]
b.sort()
d={}
m=0
for c in range(n):
    if b[c]==m:
        d[m]=d[m]+1
    else:
        m=b[c]
        d[m]=1
s=0
for c in d:
    s=s+(d[c]*(d[c]-1))//2
for c in a:
    print(s-d[c]+1)

Submission status: Accepted

Solution code:
n =int(input())
a = list(map(int,input().split()))
b = []
x = {}
def fx(x) :
    ans = 0
    for i in range(1,x):
        ans += i
    return ans
for i in a :
    if i in x :
        x[i] += 1
        if x[i] == 2:
            b.append(i)
    else :
        x[i] = 1
anskari = 0
for i in b :
    anskari += fx(x[i])
for i in a :
    if x[i] == 1:
        print(anskari)
    else :
        print(anskari - x[i] +1)