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: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
# a = [i+1 for i in range(n)]
dct = {}
for i in range(n):
    if a[i] in dct:
        dct[a[i]] += 1
    else:
        dct[a[i]] = 1
tmp3_dct = dct
dct = {}
for key, value in tmp3_dct.items():
    if value > 1:
        dct[key] = value
# print(dct)
tmp_dct = {}
tmp2_dct = {}
for key, value in dct.items():
    tmp_dct[key] = value * (value - 1) // 2
    tmp2_dct[key] = (value - 1) * (value - 2) // 2
# print(tmp_dct, tmp2_dct)
ans_dct = {}
for key, value in dct.items():
    cnt = 0
    for key2, value2 in dct.items():
        if key == key2:
            cnt += tmp2_dct[key2]
        else:
            cnt += tmp_dct[key2]
        # print(key, key2, cnt)
    ans_dct[key] = cnt
# print(ans_dct)
for i in range(n):
    if a[i] in ans_dct:
        print(ans_dct[a[i]])
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
nMax = 2 * 10 ** 5
lmemo = [-1] * (nMax + 1)
def fperm(a, b):
  if a < b:
    return 0
  nump = 1
  for i in range(b, a + 1):
    nump *= i
  return nump

def fcomb(a, b):
  if a < b:
    return 0
  if lmemo[a] != -1:
    return lmemo[a]
  else:
    return fperm(a, b) // math.factorial(b)
  
l = [0] * (nMax + 1)
ldef = [0] * (nMax + 1)

ak = list(map(int, input().split()))
numMax = 0
for num in ak:
  l[num] += 1
  if num > numMax:
    numMax = num
ctotal = 0
for i in range(numMax + 1):
  if l[i] >= 2:
    com = fcomb(l[i], 2)
    ctotal += com
    ldef[i] = fcomb(l[i] - 1, 2) - com
for num in ak:
  total = ctotal + ldef[num]
  print(total)

Submission status: Wrong Answer

Solution code:
N_max = 2*(10**5)
N = int(input())

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

array = sorted(A)
quantity_of_num = [0]*(N_max + 1) # kという値がquantity_of_num[k]個あることを示す
type_index = list() # 文字の種類を昇順で記録していく配列。　len(type_index)が文字の種類数

count = 1 # 各文字が何個あるかの記録作業
for i in range(N-1):
    if array[i] == array[i+1]:
        count += 1
    else:
        type_index.append(array[i])
        quantity_of_num[array[i]] = count

        count = 1
type_index.append(array[i])
quantity_of_num[array[i]] = count

# for i in range(len(type_index)):
#     print(type_index[i], end="")
# print()
# for i in range(len(type_index)):
#     print(quantity_of_num[type_index[i]], end="")
# print()

total = 0 #k番目を除外せずに同じ数字の取り方が何通りあるかを検証
for i in range(len(type_index)):
        quantity = quantity_of_num[type_index[i]]
        # print("i = ", i, "quantitiy = ", quantity, "sum = ", quantity*(quantity - 1) // 2)
        total += quantity*(quantity - 1) // 2

for k in range(N):

    # k番目の数字から選んでいた部分を修正すれば良い
    # A[k] がk番目の数字
    quantity = quantity_of_num[A[k]]
    ans = total - ( quantity*(quantity-1) // 2) + ( (quantity-1)*(quantity-2) // 2)
    
    print(ans)

Submission status: Wrong Answer

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):
    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: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=[]
from collections import Counter
MOD=10**9+7
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%MOD
    for i in range(2,k+1):
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        ans=ans*(n-k+i)*inv[i]%MOD
    return ans
cnt=[]
v=set()
yut=True
for i in range(n-1):
    if a[i]!=a[i+1]:
        yut=False
if yut:
    for i in range(n):
        print(comb(n-1,2))
    exit()
d=Counter(a)
for i in range(n):
    g=d[a[i]]
    v.add(a[i])
    cnt.append([a[i],comb(g,2)])
fg=0
cvg=[]
vsd=list(v)
for i in range(n):
    tt=vsd[fg]
    if cnt[i][0]==tt:
        cvg.append(cnt[i][1])
        if  fg<len(vsd)-1:
            fg+=1
cvg.remove(cvg[-1])
sy=sum(cvg)
for i in range(n):
    h=d[a[i]]
    tmp=sy-(h-1)
    ans.append(tmp)

for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    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
N=int(input())
count=[0]*N
A=list(map(int,input().split()))
for i in range(N):
    count[A[i]-1]+=1
#print(count)
k=max(count)
kari=count.copy()
kari.sort()
tekitou=kari[1]
#print(k)
ans=0
for i in range(N):
    if count[i]>=2:
        ans+=cmb(count[i],2)
#print(ans)
for i in range(N):
    unti=count[A[i]-1]
    #print(unti,"unti")
    if count[A[i]-1]==k:
        print(ans-cmb(k,2)+cmb(k-1,2))
    else:
        if unti>2:
            print(ans-cmb(unti,2)+cmb(unti-1,2))
        else:
            print(ans-cmb(unti,2))

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
a = input().split()

for i in range(n):
  b = copy.copy(a)
  del b[i]
  k = 0
  c = set(b)
  for t in c:
    num = b.count(t)
    
    print('num',num)
    for i in range(num):
      k += i
  print(k)

Submission status: Wrong Answer

Solution code:
# 200322 D

import collections

def cmb(n, r):
    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


N = int(input())
A = list(map(int,input().split()))
gAc = collections.Counter(A)
bAc = {}
bAc = gAc

for i in range(len(A)):
    Ac = bAc
    Ac[A[i]] -= 1
    cmbsum = 0
    for j in Ac:
        if Ac[j] <= 1:
            cmbsum += 0
        else:
            cmbsum += cmb(Ac[j],2)
    print(cmbsum)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=[0]*200001
s=0
t=0
nsum=0
for i in range(n):
    c[a[i]]+=1
for j in range(n):
    nsum+=max(c[j]*(c[j]-1)/2,0)
for k in range(n):
    s=c[a[k]]
    t=(nsum+1-s)
    print(int(t))

Submission status: Wrong Answer

Solution code:
import copy

def n_sum(n):
  x = 1
  ans_sum = 0
  while x <= n:
    ans_sum += x
    x += 1

  return ans_sum

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


new_a = list(set(a))
dummy_a = copy.deepcopy(new_a)

for i in range(len(new_a)):
  dummy_a[i] = a.count(new_a[i])

print(dummy_a)
for i in a:
  dummy_b = copy.deepcopy(dummy_a)
  dummy_b[new_a.index(i)] -= 1
  ans = 0
  for j in dummy_b:
    ans += n_sum(j - 1)
  print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
k = [int(i) for i in input().split()]
pair = {}

for i in range(n):
    pair.setdefault(k[i], []).append(i)

sum = 0
for value in pair.values():
    l = len(value)
    sum += l*(l-1)//2

for i in range(n):
    ans = 0
    len_pair = len(pair[k[i]])
    if len_pair != 1:
        ans = sum - ((len_pair*(len_pair-1)//2)-((len_pair-1)*(len_pair-2)//2))
        print(ans)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	ap = {}
	for i in A:
		if i in ap:
			ap[i] += 1
		else:
			ap[i] = 1

	mmax = 0
	for k, v in ap.items():
		if v > 1:
			mmax += cmb(v, 2)

	#print(mmax)
	for i in A:
		conts = ap[i]
		conts2 = conts -1
		#print("{} {}".format(conts, conts2))

		m = cmb(conts, 2)
		p = cmb(conts2, 2)

		#print("{} {}".format(m, p))
		if conts < 3:
			p = 0
		#print("{} {}".format(m, p))
		aaa = mmax - m + p
		print(max(aaa,0))


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def cmb(n, r):
    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

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n = int(input())
# a = list(map(int, input().split()))
a = [i+1 for i in range(n)]
dct = {}
for i in range(n):
    if a[i] in dct:
        dct[a[i]] += 1
    else:
        dct[a[i]] = 1
tmp3_dct = dct
dct = {}
for key, value in tmp3_dct.items():
    if value > 2:
        dct[key] = value
tmp_dct = {}
tmp2_dct = {}
for key, value in dct.items():
    tmp_dct[key] = value * (value - 1) // 2
    tmp2_dct[key] = (value - 1) * (value - 2) // 2
# print(tmp_dct, tmp2_dct)
ans_dct = {}
for key, value in dct.items():
    cnt = 0
    for key2, value2 in dct.items():
        if key == key2:
            cnt += tmp2_dct[key2]
        else:
            cnt += tmp_dct[key2]
        # print(key, key2, cnt)
    ans_dct[key] = cnt
# print(ans_dct)
for i in range(n):
    if a[i] in ans_dct:
        print(ans_dct[a[i]])
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	ap = {}
	for i in A:
		if i in ap:
			ap[i] += 1
		else:
			ap[i] = 1

	mmax = 0
	for k, v in ap.items():
		if v > 1:
			mmax += cmb(v, 2)

	print(mmax)
	for i in A:
		conts = ap[i]
		conts2 = conts -1
		#print("{} {}".format(conts, conts2))

		m = cmb(conts, 2)
		p = cmb(conts2, 2)

		#print("{} {}".format(m, p))
		if conts < 3:
			p = 0
		#print("{} {}".format(m, p))
		aaa = mmax - m + p
		print(max(aaa,0))


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def cmb(n, r):
    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

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import copy
from scipy.misc import comb
 
n = map(int, input())
a = list(map(int, input().split()))
matches = {}
 
for i in range(len(a)):
  aa = copy.copy(a)
  del aa[i]
  for av in aa:
    if av in matches:
      matches[av] += 1
    else:
      matches[av] = 1
  combi_cnt = 0
  for v in matches:
    combi_cnt += comb(v, 2, exact=True)
  print(combi_cnt)
  matches = {}

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

nn = int(input())
aa = list(map(int, input().split(' ')))

counts = {}
max_v = 0
for a in aa:
    if a not in counts:
        counts[a] = aa.count(a)
        if max_v < counts[a]:
            max_v = counts[a]
if max_v == 1:
    for k in range(nn):
        print(0)


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(1, r + 1))


results = {}
for a, c in counts.items():
    if a in results:
        continue
    count = 0
    for aaa, cc in counts.items():
        if a == aaa:
            cc -= 1
        if cc <= 1:
            continue
        if cc <= 2:
            count += 1
            continue
        count += cmb(cc, 2)
    results[a] = int(count)

for k in range(nn):
    print(results[aa[k]])

Submission status: Wrong Answer

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+1)
memo_cmb = [0]*(n+1)
memo_cmb2 = [0]*(n+1)

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

for i in range(n):
    
    if memo_cnt[i] >= 3:
        memo_cmb[i] = cmb(memo_cnt[i],2)
        memo_cmb2[i] = cmb(memo_cnt[i]-1,2)
    elif memo_cnt[i] == 2:
        memo_cmb[i] = cmb(memo_cnt[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: Wrong Answer

Solution code:
import math
import collections

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

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

for i in range(N):
    result = 0
    pop = A.pop(i)
    c = collections.Counter(A)
    v = c.values()
    for i in v:
        if i > 1:
            result = result + combinations_count(i, 2)
    A.insert(i, pop)
    print(result)

Submission status: Wrong Answer

Solution code:
# 200322 D

import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    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

N = int(input())
A = list(map(int,input().split()))
gAc = collections.Counter(A)
bAc = {}
bAc = gAc

for i in range(len(A)):
    Ac = bAc
    Ac[A[i]] -= 1
    cmbsum = 0
    for j in Ac:
        if Ac[j] <= 1:
            cmbsum += 0
        else:
            cmbsum += cmb(Ac[j],2)
    print(cmbsum)

Submission status: Wrong Answer

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

for i in range(1, n+1):
  p = a.pop(-i)
  ans = len(a) - a.count(p)
  anslist.append(ans)
  a.append(p)

for j in reversed(anslist):
  print(j)

Submission status: Wrong Answer

Solution code:
def f(n):
    if n==0:
        return 0
    return n*(n-1)/2
N=int(input())
A=list(map(int,input().split()))
if len(set(A))==N:
    print(0)
    exit()
d=dict()
for i in range(N):
    if A[i] not in d:
        d[A[i]]=0
    d[A[i]]+=1
for i in range(N):
    ans=0
    for j in d:
        if j==A[i]:
            ans+=f(d[j]-1)
            continue
        ans+=f(d[j])
    print(int(ans))

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
wlists = collections.Counter(A)
print(wlists)
print(wlists[1])
print(wlists[2])
sum_num = 0
for i in wlists:
  sum_num += wlists[i] * (wlists[i] - 1) // 2
print("num_sum:{}".format(sum_num))
for i in range(N):
  num = sum_num - wlists[A[i]] * (wlists[A[i]] - 1) // 2
  if wlists[A[i]] > 1:
    num += (wlists[A[i]] - 1) * (wlists[A[i]] - 2) // 2
  print(num)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
lis = [0] * (n *2)
for i in range(n):
    lis[a[i]] += 1
#print(lis)
cum = [0] * len(lis)
for i in range(n):
    cnt = (lis[i] * (lis[i]-1)) // 2
    cum[i] = cnt
ans = sum(cum)
cum2 = [0] * len(lis)
for i in range(2,(n*2)):
    cum2[i] = (i * (i-1)) // 2
#print(cum)
#print(cum2)
#cum2がiに対しての組み合わせ
#cumが要素数に対しての組み合わせ
#lisがiの数
#print(ans)
for i in range(n):
    print(ans - (cum2[lis[a[i]]]-cum2[lis[a[i]]-1]))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = input().split()
c = Counter(A)
a = list(c.values())
b = len(a)
print(a,b)
AA = A
for i in range(N):
    r = 0
    x = AA.pop(i)
    c = Counter(AA)
    a = list(c.values())
    b = len(a)
    for j in range(b):
        r += (a[j]*(a[j]-1))/2
    AA.insert(i,x)
    print(int(r))

Submission status: Wrong Answer

Solution code:
import collections
import math


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


N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
memo = {}
ans = 0
for k, v in c.items():
    if v > 1:
        memo[k] = combinations_count(v, 2)
        ans += memo[k]
total_ans = ans

for i in range(N):
    k_ball = A[i]
    if c[k_ball] > 2:
        print(int(total_ans - (memo[k_ball] - memo[k_ball] / c[k_ball])))
    elif c[k_ball] > 1:
        # 2
        print(total_ans - 1)
    else:
        print(total_ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
k = []
q = []
for i in range(n):
    t = a[i]
    if t in k:
        q[k.index(t)] += 1
    else:
        k.append(t)
        q.append(1)
M = 0
print(k)
print(q)
for i in q:
    if i > 1:
        M += i*(i-1)//2
print(M)
for i in range(n):
    w = a[i]
    if w in k:
        m = q[k.index(w)]
        print(M-m+1)
    else:
        print(M)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


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

dd = defaultdict(int)

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

count = 0
for k, v in dd.items():
    if v >= 2:
        count += nCr(v, 2)
for i in range(N):
    if dd[A[i]] >= 3:
        ans = count - nCr(dd[A[i]], 2) + nCr(dd[A[i]]-1, 2)
    elif dd[A[i]] == 2:
        ans = count - nCr(dd[A[i]], 2)
    else:
        ans = count
    print(ans)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

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

aa = [0 for i in range(2*10**5)]
for i in range(n):
  aa[a[i]] += 1
aa.sort(reverse=True)
 
for i in range(n):
  ans = 0
  aa[a[i]] -= 1
  for key in range(2*10**5):
    if aa[key] > 1:
      ans += comb(aa[key], 2)
    else:
      break
  aa[a[i]] += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
lis = [0] * (n + 3)
for i in range(n):
    lis[a[i]] += 1
#print(lis)
cum = [0] * len(lis)
for i in range(n):
    cnt = (lis[i] * (lis[i]-1)) // 2
    cum[i] = cnt
ans = sum(cum)
cum2 = [0] * len(lis)
for i in range(2,n+2):
    cum2[i] = (i * (i-1)) // 2
#print(cum)
#print(cum2)
#cum2がiに対しての組み合わせ
#cumが要素数に対しての組み合わせ
#lisがiの数
#print(ans)
for i in range(n):
    print(ans - (cum2[lis[a[i]]]-cum2[lis[a[i]]-1]))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=[]
from collections import Counter
MOD=10**9+7
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%MOD
    for i in range(2,k+1):
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        ans=ans*(n-k+i)*inv[i]%MOD
    return ans
cnt=[]
v=set()
yut=True
for i in range(n-1):
    if a[i]!=a[i+1]:
        yut=False
if yut:
    for i in range(n):
        print(comb(n-1,2))
    exit()
d=Counter(a)
for i in range(n):
    g=d[a[i]]
    v.add(a[i])
    cnt.append([a[i],comb(g,2)])
fg=0
cvg=[]
vsd=list(v)
for i in range(n):
    tt=vsd[fg]
    if cnt[i][0]==tt:
        cvg.append(cnt[i][1])
        if  fg<len(vsd)-1:
            fg+=1

sy=sum(cvg)-cvg[-1]
for i in range(n):
    h=d[a[i]]
    tmp=sy-(h-1)
    ans.append(tmp)

for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
a = [int(i) for i in input().split(' ')]
c = collections.Counter(a)
counts = {}
all_sum = 0
for k, v in c.items():
    val = v * (v-1) / 2
    counts[k] = val
    all_sum += val

for i in range(n):
    k = a[i]
    count = c[k] - 1
    val = counts[k]
    print(all_sum - val + count * (count - 1) / 2)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np

N = int(input())
arr = np.array(list(map(int, input().split(" "))))
#val, count = np.unique(arr, return_counts=True)
count = np.bincount(arr)

for i in range(len(arr)):
    k_val = arr[i]
    count[k_val] -= 1
    conv = (count * (count - 1) / 2).astype(int)
    print(np.sum(conv))

Submission status: Wrong Answer

Solution code:
import collections

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

ctr_A = collections.Counter(A).most_common()
less_A = collections.Counter(A)

total = 0

for i in range(len(ctr_A)):
    n = ctr_A[i][1]
    total += n * (n - 1) // 2

for i in range(N):
    summ = total
    num = A[i]
    n = less_A[num]

    if (n <= 2):
        summ -= 1
    else:
        new = (n - 1) * (n - 2) // 2
        old = n * (n - 1) // 2
        summ += new - old
    
    ans = max(0, summ)

    print(ans)

Submission status: Wrong Answer

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

while count < n:
  p = a.pop(0)
  ans = len(a) - a.count(p)
  print(ans)
  a.append(p)
  count += 1

Submission status: Wrong Answer

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

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

N = int(input())
L = list(map(int, input().split()))
M = [0] *(N+1)

for i in L:
    M[i] += 1
ans = 0
for i in range(N):
  A = M[i]
  if A >= 2:
  	ans += combinations_count(A, 2)
for i in range(N):
  A = L[i]
  B = M[A]
  if B == 2:
  	print(ans - 1)
  elif B > 2:
    print(ans -combinations_count(B,2) +combinations_count(B-1,2))
  else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import Counter
import math


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = Counter(A)
    dict = {}
    for key, value in c.items():
        if value > 1:
            dict[key] = combinations_count(value, 2)

    for a in A:
        cnt = 0
        for key, value in dict.items():
            if key == a and c[a] - 1 > 1:
                cnt += combinations_count(c[a] - 1, 2)
            else:
                cnt += value

        print(cnt)


if __name__ == "__main__":
    main()