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 numpy as np
N = int(input())
A = np.array(list(map(int, input().split(' '))))
num_sum = 0
remove_array = np.array([], int)
for i in range(N):
    c1 = np.count_nonzero(A == i + 1)
    c2 = np.count_nonzero(A == A[i])
    if c2 <= 1:
        remove_array = np.append(remove_array, 0)
    else:
        remove_array = np.append(remove_array, c2 - 1)
    num_sum += int(c1 * (c1 - 1) / 2)
print(*(num_sum - remove_array), sep='\n')
'''
import collections
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
total = 0
for key in cnt.keys():
    total += cnt[key] * (cnt[key] - 1) // 2
for i in range(N):
    tmp = total
    tmp -= cnt[A[i]] * (cnt[A[i]] - 1) // 2
    tmp += (cnt[A[i]] - 1) * (cnt[A[i]] - 2) // 2
    print(tmp)

Submission status: Accepted

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

c = Counter(nums)
a = 0
for k,v in c.items():
    if v >=2:
        a+=(v-1)*v//2

for num in nums:
    curr = -1
    if c[num] >= 2:
        curr = a - (c[num]-1)
    else:
        curr = a
    print(curr)

Submission status: Accepted

Solution code:
import collections
import math
def calculateProb(counts):
    ways = 0
    for key in counts.keys():
        if counts[key] < 2:
            continue
        else:
            val = counts[key]
            ret = val*(val-1)/2
            ways += ret
    return ways

def getfact(val):
    if val < 2:
        return 0
    return val*(val-1)/2


n = int(input())

values = list(map(int, input().split(' ')))
counts = collections.Counter(values)

ways = calculateProb(counts)
for k in range(n):
    curVal = values[k]
    count = counts[curVal]
    temp = ways
    ways = ways - getfact(count)  + getfact(count - 1)
    print(int(ways))
    ways = temp

Submission status: Accepted

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

for i in range(N):
  k = A[i]
  change = (a[k]-1)*(a[k]-2)/2
  print(int(total-B[k]+change))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
dic1 = {}
dic2 = {}
for i in range(N):
  if A[i] in dic1:
    dic1[A[i]] += 1
  else:
    dic1[A[i]] = 1
ans = 0
for v in dic1.values():
  ans += (v*(v-1))//2
for j in range(N):
  w = dic1[A[j]]
  v = w-1
  comb = ans -(w*(w-1))//2 + (v*(v-1))//2
  print(comb)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
d=dict()

for i in range(len(l)):
  d.setdefault(l[i],0)
  d[l[i]] += 1

result=0

for key,value in d.items():
    num=(value*(value-1))/2
    result += num

for i in range(len(l)):
    r1=int((d[l[i]]*(d[l[i]]-1))/2)
    r2=int(((d[l[i]]-1)*(d[l[i]]-2))/2)
    output=int(result-r1+r2)
    print(output)

Submission status: Accepted

Solution code:
def Comb(n,k):
    comb_ans=1
    for i in range(1,k+1):
        comb_ans*=(n-i+1)/i
    comb_ans=int(comb_ans)
    return comb_ans

N=int(input())
A=list(map(int,input().split()))
ans=0
B=set(A)
L=[0]*N
for i in range(N):
    L[A[i]-1]+=1
for i in B:
    ans+=Comb(L[i-1],2)
for i in range(N):
    pri=ans
    pri=ans-L[A[i]-1]+1
    print(pri)

Submission status: Accepted

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

dic = {}

for i in A:
    if i in dic:
        dic[i] = dic[i] + 1
    else:
        dic[i] = 1


dic2 = {}


ans = 0
for key,value in dic.items():
    ans = ans + int(value * (value-1) / 2)

diff_dic = {}

for key,value in dic.items():
    diff_dic[key] = int((value*(value-1)/2) - ((value-1)*(value-2)/2))


for i in A:
    print(ans-diff_dic[i])

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
l = [int(i) for i in input().split()]

c = Counter(l)

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

Submission status: Accepted

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

from collections import Counter
c = Counter(l)
x = list(c.values())

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

y = 0
for i in range(len(x)):
    if x[i] != 1:
        y += combinations_count(x[i], 2)

for j in range(n):
    print(y - (c[l[j]] - 1))

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
al = list(map(int, input().split()))
al_cnt = Counter(al)
ans = sum([i * (i - 1) // 2 for i in al_cnt.values()])
for j in al:
    print(ans - al_cnt[j] + 1)

Submission status: Accepted

Solution code:
N = int(input())
B = list(map(int, input().split()))
count = {}

for i in B:
  if i in count:
    count[i] += 1
  else:
    count[i] = 1
    
total = 0
for i in count:
  total += count[i]*(count[i]-1)/2
  
for i in range(N):
  k = count[B[i]]
  print(int(total-k+1))

Submission status: Accepted

Solution code:
from collections import Counter

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

d = Counter(A)
k = d.keys()

# print(d, k)


def nC2(x):
    return x * (x - 1) // 2


total = 0
for kk in k:
    total += nC2(d[kk])

# print(total)

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

Submission status: Accepted

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

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

cnt = [0]*(n+1)
total = 0
ans = 0

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

for i in range(1, n+1):
    total += nC2(cnt[i])

for i in range(n):
    print(total - nC2(cnt[a[i]]) + nC2(cnt[a[i]] - 1))

Submission status: Accepted

Solution code:
from collections import Counter

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


def comb(x):
    if x == 0:
        return 0
    if x == 1:
        return 0
    return x * (x - 1) // 2


d = Counter(A)
# print(d)
k = d.keys()

# print(k)
total = 0

for kk in k:
    total += comb(d[kk])

# print(total)

for a in A:
    res = total
    res -= comb(d[a])
    res += comb(d[a] - 1)
    print(res)

Submission status: Accepted

Solution code:
from collections import Counter as cnt
n =  int(input())
A = list(map(int, input().split()))
dic = cnt(A)
total = 0
for num in dic.values():
  if num >= 2:
    total += num * (num - 1) // 2
    
for num in A:
  target = dic[num]
  ans = total
  if target >= 2:
    ans -= target * (target - 1) // 2
    ans += (target - 1) * (target - 2) // 2
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from collections import Counter
from bisect import bisect_left

def calc(d, i, dsum, m):
    return comb(d, i) + dsum[i] + dsum[m] - dsum[i+1]

def comb(d, i):
    return d[i][1] * max(0, d[i][1] - 1) // 2

def main():
    n = int(input().strip())
    v = list(map(int, input().strip().split()))
    d = [[k, v] for k, v in sorted(dict(Counter(v)).items())]
    keys = [q[0] for q in d]
    m = len(d)
    dsum = [0] * (n+1)
    for i in range(1, m+1):
        dsum[i] = dsum[i-1] + comb(d, i-1)
    for i in range(n):
        j = bisect_left(keys, v[i])
        d[j][1] -= 1
        print(calc(d, j, dsum, m))
        d[j][1] += 1

if __name__ == '__main__':
    main()

Submission status: Accepted

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

datas = [0] * (n+1)
for a in an:
    datas[a] += 1

ans = 0
for i in range(1,n+1):
    if datas[i] > 1:
        ans += datas[i] * (datas[i]-1)/2
ans = int(ans)

for k in range(0,n):
    if datas[an[k]] > 1:
        print(int(ans - datas[an[k]] * (datas[an[k]]-1)/2 + (datas[an[k]]-1) * (datas[an[k]]-2)/2))
    else:
        print(ans)

Submission status: Accepted

Solution code:
import collections
import math
def C(n):
    return n * (n-1) // 2
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
d = {}
sm = 0
for k,v in c.most_common():
    d[k] = v
    sm += C(v)
for a in A:
    print (sm - C(d[a]) + C(d[a]-1))

Submission status: Accepted

Solution code:
from collections import Counter

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

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

ans = []
for a in A:
    ans.append(S - (cntA[a] - 1))

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
c = {}
for k in range(N):
    if c.get(A[k]) is None:
        c[A[k]] = 1
    else:
        c[A[k]] += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

#output
from collections import  Counter
L = Counter(A)

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

for i in range(N):
    print(original_answer - (L[A[i]]*(L[A[i]]-1))//2 + ((L[A[i]]-1)*(L[A[i]]-2))//2)

Submission status: Accepted

Solution code:
import collections

num = int(input())
a_i = list(map(int, input().split()))
anslist = collections.Counter(a_i)

ans = 0
for x in anslist.values():
    ans += x * (x - 1) // 2
for x in range(num):
    val = a_i[x]
    cnt = anslist[val]
    print(ans - (cnt - 1))

Submission status: Accepted

Solution code:
import collections

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

ans=0
dic=collections.Counter(A)
keys=list(dic.keys())
values=list(dic.values())


for i in values:
    
    ans+=(i*(i-1))//2

for j in A:
    ANS=ans
    num=dic[j]
    ANS=ANS-(num-1)
    print(ANS)

Submission status: Accepted

Solution code:
from collections import Counter


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

    cnt = Counter(arr)
    total = 0
    for key in cnt.keys():
        total += cnt[key]*(cnt[key]-1)//2

    for i in range(n):
        tmp = total
        tmp -= cnt[arr[i]]*(cnt[arr[i]]-1)//2
        tmp += (cnt[arr[i]]-1)*(cnt[arr[i]]-2)//2
        print(tmp)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a_counter = Counter(a)
total = 0
for i in a_counter.values():
    total += i*(i-1)/2
for j in a:
    print(int(total-(a_counter[j]-1)))

Submission status: Accepted

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

se = set()
dic = dict()

for i in range(N):
    if A[i] in se:
        dic[A[i]] += 1
    else:
        se.add(A[i])
        dic.update({A[i]: 1})

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

for i in range(N):
    print(c - dic[A[i]]+1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
li = [0 for i in range(N)]

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

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

Submission status: Accepted

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

cnt = Counter(A)
cnt_key = list(cnt.values())

ans = 0

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

for j in A:
    m = cnt[j]
    print(ans - m*(m-1)//2 + (m-1)*(m-2)//2)

Submission status: Accepted

Solution code:
def CountFrequency_mod(my_list): 
  
    # Creating an empty dictionary  
    freq = {} 
    for item in my_list: 
        if (item in freq): 
            freq[item] += 1
        else: 
            freq[item] = 1
    
    freq_mod = freq
    freq_val = list(freq.values())
    all_sum=0
    
    for i in freq_val:
        all_sum+=i*(i-1)/2
        
    for i in freq:
        freq_mod[i] = all_sum - freq[i]*(freq[i]-1)/2 + (freq[i]-1)*(freq[i]-2)/2
    return freq_mod


N = int(input())

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

dic = CountFrequency_mod(A)

for i in A:
    print(int(dic[int(i)]))

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=list(map(int,input().split()))
b = collections.Counter(a)
total = 0

for i in b.values():
  total += i*(i-1)//2
  
for i in a:
  c = b[i]
  print(total-(c*(c-1)//2)+((c-1)*(c-2)//2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
*a,= map(int, input().split())
count={}

for i in range(N):
  count[a[i]]=0
  
def ncn(n):
  return n*(n-1)//2

for i in range(N):
  count[a[i]]+=1

total=0
for key in count.keys():
  kc = count[key]
  total += ncn(kc)
  
def without(k):
  return total-count[a[k]] + 1

for k in range(N):
  print(without(k))

Submission status: Accepted

Solution code:
N = int(input())
*a,= map(int, input().split())
count,result={},{}

for i in range(N):
  count[a[i]]=0
  result[a[i]]=0
  
def ncn(n):
  return n*(n-1)//2

for i in range(N):
  count[a[i]]+=1

total=0
for key in count.keys():
  kc = count[key]
  result[key]=ncn(kc)
  total += result[key]
  
def without(k):
  return total-count[a[k]] + 1

for k in range(N):
  print(without(k))

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=list(map(int,input().split()))
b=collections.Counter(a)
e=0
for x in b.values():
    e+=x*(x-1)
for x in a:
    t=b[x]
    p=e-t*(t-1)+(t-1)*(t-2)
    print(p//2)

Submission status: Accepted

Solution code:
c=[0]*8**6
_,a=open(0)
*a,=map(int,a.split())
for i in a:c[i]+=1
s=sum(i*~-i//2for i in c)
for i in a:print(s-2*~-c[i]//2)

Submission status: Accepted

Solution code:
# D - Banned K
from collections import Counter


def main():
    N, *A = map(int, open(0).read().split())
    cnt = Counter(A)
    total = sum(v * (v - 1) // 2 for k, v in cnt.items())
    ans = [total - (cnt[a] - 1) for a in A]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Banned K
from collections import Counter


def main():
    N, *A = map(int, open(0).read().split())
    counter = Counter(A)
    total = 0
    dif = {}
    for k, v in counter.items():
        total += v * (v - 1) // 2
        dif[k] = v - 1
    ans = [total - dif[a] for a in A]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Banned K
from collections import Counter


def main():
    N, *A = map(int, open(0).read().split())
    counter = Counter(A)
    total = 0
    dif = {}
    for k, v in counter.items():
        total += max(0, v * (v - 1) // 2)
        dif[k] = max(0, v - 1)
    ans = [total - dif[a] for a in A]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Banned K
from collections import Counter


def main():
    N, *A = map(int, open(0).read().split())
    counter = Counter(A)
    patterns, less_patterns = {}, {}
    for k, v in counter.items():
        patterns[k] = max(0, v * (v - 1) // 2)
        less_patterns[k] = max(0, (v - 1) * (v - 2) // 2)
    total = sum(patterns.values())
    ans = [total - patterns[a] + less_patterns[a] for a in A]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

A_counter = Counter(A)
ans = 0
for A_content in A_counter.values():
  ans += A_content * (A_content-1)//2


for i in range(len(A)):
  dif = 0
  if A_counter[A[i]] > 1:
    dif = A_counter[A[i]] - 1
  print(ans - dif)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
e=list(set(a))
s=0
t=[0]*200000
for i in a:
    t[i]+=1
for j in e:
    k=t[j]
    s+=(k*(k-1))//2
for u in a:
    print(s-t[u]+1)

Submission status: Accepted

Solution code:
import collections
import math
def P(n,r):
    return math.factorial(n) // math.factorial(n-r)
def C(n,r):
    return P(n,r) // math.factorial(r)
n = int(input())
a = list(map(str,input().split()))
c = collections.Counter(a)
s = 0
for i in list(c.values()):
    s += i*(i-1)//2
for i in a:
    ans = s - (int(c[str(i)] - 1))
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
aset=list(set(a))
ans=0
al=[0]*200000
for i in a:
    al[i]+=1
for j in aset:
    k=al[j]
    ans+=(k*(k-1))//2
for u in a:
    print(ans-al[u]+1)

Submission status: Accepted

Solution code:
import collections
def I(): return int(input())
def LI(): return list(map(int,input().split()))
##################################################
N = I()
A = LI()
count = collections.Counter(A)
sum = 0
for x in count.values():
    sum += x*(x-1)//2
for x in A:
    temp = count[x]
    minus = temp*(temp-1)//2
    plus = (temp-1)*(temp-2)//2
    print(sum-minus+plus)

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):
      print(int(j-(c[a[i]]-1)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from sys import stdin

N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))

cnt = Counter(A)


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


sumall = 0

for i in cnt.values():
    sumall += comb(i)

for a in A:
    ans = sumall - (cnt[a] - 1)
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

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

num = [0]*(N+1)
for i in range(N+1):
    num[i] = d[i]

s = 0
for i in range(N+1):
    s += num[i]*(num[i]-1)//2
    
for i in range(1,N+1):
    print(s-(d[A[i-1]])+1)

Submission status: Accepted

Solution code:
import math
import collections


def kumiawase(n):
    if n == 0 or n == 1:
        return 0
    return (n**2 - n) // 2


n = int(input())
aL = list(map(int, input().split(" ")))

d = collections.Counter(aL)

s = 0
for i in d.values():
    s += kumiawase(i)

for a in aL:
    print(s - kumiawase(d[a]) + kumiawase(d[a] - 1))

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

def ncr(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

a = int(input())
A = list(map(int, input().split()))  
d = {}
for k in A:
  if k in d:
    d[k] += 1
  else:
    d[k] = 1
 
res = 0
for k in d:
    if d[k] >= 2:
      res += ncr(d[k], 2)

for k in A:
  temp = res
  m = d[k]
  d[k] -= 1
  if m >= 2:
    temp -= ncr(m, 2)

  if d[k] >= 2:
    temp += ncr(d[k], 2)
  print(temp)
  d[k] += 1

Submission status: Accepted

Solution code:
def I(): return int(input())
def LI(): return list(map(int,input().split()))
##################################################
N = I()
A = LI()
count = [0]*(N+1)
for x in A:
    count[x] += 1
nC2 = {}
sum = 0
for x in count:
    nC2[x] = x*(x-1)//2
    sum += nC2[x]
for x in count:
    if x-1 in nC2 or x==0:
        continue
    nC2[x-1] = (x-1)*(x-2)//2
for x in A:
    minus = nC2[count[x]]
    plus = 0 if count[x]==0 else nC2[count[x]-1]
    print(sum-minus+plus)

Submission status: Accepted

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

def combination2(n, r):
    if n <= 1:
        return 0
    return math.factorial(n) / (math.factorial(r) * math.factorial(n-r))

def combination(n, r):
    # X = n * n-1 * ... * max(r, n - r)+1
    # Y = min(r, n - r)!
    # nCr = X / Y
    if n <= 1:
        return 0

    X = 1
    for i in range(n, max(r, n - r), -1):
        X *= i
    
    if n - r <= 0:
        return X

    Y = math.factorial(min(r, n - r))

    return X / Y

class UnionFindTree():
    def __init__(self, n):
        self.parent = [] # 親のノード
        self.rank = [] # 木の深さ
        self.number = [] # グループの要素数
        for i in range(n):
            self.parent.append(i)
            self.rank.append(0)
            self.number.append(1)

    # 根ノードを取得
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.number[y] += self.number[x]
        else:
            self.parent[y] = x
            self.number[x] += self.number[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じノードか判別
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # グループのノード数を取得
    def member_number(self, x):
        x = self.find(x)
        return self.number[x]

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

uft = UnionFindTree(N)

vals = {}
for i in range(N):
    if A[i] in vals:
        uft.unite(vals[A[i]], i)
    else:
        vals[A[i]] = i

comb = {}
group_numbers = {}
total = 0
comb_memo = {}
for k, v in vals.items():
    group_number = uft.member_number(v)
    if group_number not in comb_memo:
        comb_memo[group_number] = combination(group_number, 2)
    comb[k] = comb_memo[group_number]

    group_numbers[k] = group_number
    total += comb[k]

ans = {}
for k, v in vals.items():
    if group_numbers[k] - 1 not in comb_memo:
        comb_memo[group_numbers[k] - 1] = combination(group_numbers[k] - 1, 2)
    ans[k] = int(total - comb[k] + comb_memo[group_numbers[k] - 1])

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

Submission status: Accepted

Solution code:

import collections


def solve(n, balls):
    counts = collections.Counter(balls)

    totalWays = 0

    for count in counts.values():
        totalWays += count*(count-1)//2

    results = []

    for ball in balls:
        waysWithoutBall = totalWays - (counts[ball]*(counts[ball]-1)//2)

        results.append(waysWithoutBall +
                       ((counts[ball]-1)*(counts[ball]-2)//2))

    return results


n = int(input().strip())
balls = list(map(int, input().strip().split()))

results = solve(n, balls)

for result in results:
    print(result)

Submission status: Accepted

Solution code:
def I(): return int(input())
def LI(): return list(map(int,input().split()))
##################################################
N = I()
A = LI()
count = [0]*(N+1)
for x in A:
    count[x] += 1
nC2 = {}
sum = 0
for x in count:
    nC2[x] = x*(x-1)//2
    sum += nC2[x]
for x in count:
    if x-1 in nC2 or x==0:
        continue
    nC2[x-1] = (x-1)*(x-2)//2
for x in A:
    minus = nC2[count[x]]
    plus = nC2[count[x]-1]
    print(sum-minus+plus)

Submission status: Accepted

Solution code:
#!python3

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


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


def main():
    w = {}
    for a in A:
        if a in w:
            w[a] += 1
        else:
            w[a] = 1
    
    v = 0
    for x in w.values():
        v += comb2(x)
    
    for a in A:
        ans = v - (comb2(w[a]) - comb2(w[a] - 1))
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import collections
from operator import mul
from functools import reduce


def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


n = int(input())
l = [int(x) for x in input().split()]
c = collections.Counter(l)

# cl = [0 for i in range(n)]
cd = {}

# print(ll)

if not c:
    for _ in range(len(l)):
        print(0)
    sys.exit()

sum = 0
for a in c:
    nc = combinations_count(c[a], 2)
    sum += nc
    # print(nc)
    # cl[i-1] = nc - int(nc*(m-2)/m)
    cd[a] = (nc - int(nc * (c[a] - 2) / c[a]))

"""
def my_index(lv):
    if lv not in c.keys():
        return sum
    else:
        return cd[lv]
"""

for lv in l:
    print(sum-cd[lv])

Submission status: Accepted

Solution code:
import math
import collections


def kumiawase(n):
    if n == 0 or n == 1:
        return 0
    return (n**2 - n) // 2


n = int(input())
aL = list(map(int, input().split(" ")))

d = collections.Counter(aL)

s = 0
for i in d.values():
    s += kumiawase(i)

for a in aL:
    print(s - d[a] + 1)

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N):
    print(int(C-(b[A[i]])+1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n = int(input())
    A = list(map(int,input().split()))
    C = Counter(A)
    total = 0
    for key, val in C.items():
        total += val * (val - 1) // 2
    for a in A:
        print(total - C[a] + 1)
resolve()

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
m=int(200200)
B=[0]*m

for i in range(n):
    B[A[i]]+=1

a=int(0)
for i in range(m):
    a+=int((B[i]-1)*B[i]/2)

for i in range(n):
    print(a-B[A[i]]+1)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
ma=int(200200)
B=[0]*ma

for i in range(n):
    B[A[i]]+=1

ans=int(0)
for i in range(ma):
    ans+=int((B[i]-1)*B[i]/2)

for i in range(n):
    print(ans-B[A[i]]+1)

Submission status: Accepted

Solution code:
from math import factorial
import collections

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

L = collections.Counter(A)

c = 0
for i in range(1,N+1):
    n = L[i]
    if n >=2:
        c += factorial(n) // factorial(2) // factorial(n - 2)

for k in range(N):
    c1 = c
    n = L[A[k]]
    if n >= 3:
        c1 -= n-1
    elif n == 2:
        c1 -= factorial(n) // factorial(2) // factorial(n-2)
    print(c1)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
l = [0]*n
ans = 0

for k,v in collections.Counter(a).items():
    l[k-1] = v
    ans += v*(v-1)//2

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
cnt = dict(Counter(a))
ans = 0
for _,c in cnt.items():
  if c >= 2:
    ans += c*(c-1)//2
    
for i in range(n):
  pop_i = a[i]
  # n(n-1)/2 - (n-1)(n-2)/2 = n-1
  dif = cnt[pop_i]-1
  print(ans-dif)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n = int(input())
s = list(map(int,input().split()))
ans = {}
#各番号がいくつずつあるのかを整理
#keyに番号、valueにその番号が書かれてあるボールの数
for i in range(n):
    if not s[i] in ans:
        ans[s[i]] = 1
    else:
        ans[s[i]] += 1
#iC2の総和
answer = 0
for i,j in ans.items():
    answer += j*(j-1)//2
#answer-nC2+(n-1)C2 = answer-n+1
#nはans[s[i]],よって以下の出力で求められる
for i in range(n):
    print(answer-ans[s[i]]+1)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
ma=int(200200)
B=[0]*ma

for i in range(n):
    now=A[i]
    B[now]+=1

ans=int(0)
for i in range(ma):
    ans+=int((B[i]-1)*B[i]/2)

for i in range(n):
    now=A[i]
    Ans=ans
    Ans-=int((B[now]-1)*B[now]/2)
    Ans+=int((B[now]-1)*(B[now]-2)/2)
    print(Ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

lis = [0]*N
ans = 0
for key, v in Counter(A).items():
	lis[key-1] = v
	ans += v*(v-1)//2

for i in range(N):
	print(ans-lis[A[i]-1]+1)

Submission status: Accepted

Solution code:
import collections

def combinations_count(n, r):
    return n * (n-1) // r


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

l1 = []
l2 = []
c = collections.Counter(l)

total = sum([combinations_count(i, 2) for i in c.values()])

for a in l:
    l1.append(combinations_count(c[a], 2))
    l2.append(combinations_count(c[a]-1, 2))
# print(l1, l2)
for i in range(len(l)):
    print(total-l1[i]+l2[i])