Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

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

1 \leq A_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

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

Sample Input 1

5
1 1 2 1 2

Sample Output 1

2
2
3
2
3

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

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

Thus, the answer for k=1 is 2.

Sample Input 2

4
1 2 3 4

Sample Output 2

0
0
0
0

No two balls have equal numbers written on them.

Sample Input 3

5
3 3 3 3 3

Sample Output 3

6
6
6
6
6

Any two balls have equal numbers written on them.

Sample Input 4

8
1 2 1 4 2 1 4 1

Sample Output 4

5
7
5
7
7
5
7
5



Sample input:
5
1 1 2 1 2


Sample output:
2
2
3
2
3

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
cnt_list = [0 for _ in range(N+1)]

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

ans_list1 = []
ans_list2 = []

for i in cnt_list:
    if i < 2:
        ans_list1.append(0)
        ans_list2.append(0)
    elif i == 2:
        ans_list1.append(1)
        ans_list2.append(0)
    else:
        ans_list1.append(i*(i-1)//2)
        ans_list2.append((i-1)*(i-2)//2)

SUM = sum(ans_list1)

for i in A:
    print(SUM - ans_list1[i] + ans_list2[i])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
a = list(Counter(A).items())
b = dict(a)

ans = 0
for i, j in a:
    ans += (j * (j-1)) // 2

for i in A:
    c = b[i]
    hiku = (c * (c-1)) // 2 
    tasu = ((c-1) * (c-2)) // 2
    print(ans - hiku + tasu )

Submission status: Accepted

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

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

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

for i in range(N):
    print(pattern - D[A[i]] + 1)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count_A = Counter(A)
n2c = {k:v*(v-1)//2 for k, v in count_A.items()}
base = sum(n2c.values())
ans = 0
for ai in A:
    count_ai = count_A[ai]
    if count_ai == 1:
        ans = base
    else:
        ans = base - n2c[ai] + ((count_ai - 1) * (count_ai - 2) // 2)
    print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n = int(input())
aaa = get_nums_l()

counts = [0] * (n+1)
patterns = [0] * (n+1)

for a in aaa:
    counts[a] += 1

for i in range(n+1):
    m = counts[i]
    patterns[i] = m * (m-1) // 2

all_patterns = sum(patterns)

for a in aaa:
    ans = all_patterns - patterns[a]
    ans += (counts[a]-1) * (counts[a]-2) // 2
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

cA = Counter(A)

binomials = [0, 0, 1]
for i in range(3, max(cA.values()) + 1):
    binomials.append(binomials[-1] * i // (i - 2))

ans0 = sum(binomials[v] for v in cA.values())

for a in A:
    print(ans0 - binomials[cA[a]] + binomials[cA[a] - 1])

Submission status: Accepted

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


counter = {}
for number in A:
    if number not in counter:
        counter[number] = 1
    else:
        counter[number] += 1

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

answer = [0] * N

for i, number in enumerate(A):
    v = counter[number]
    answer[i] = str(tmp - v * (v-1) // 2 + (v-1) * (v-2) // 2)

print('\n'.join(answer))

Submission status: Accepted

Solution code:
import collections

def solve(N, A):
    c = collections.Counter(A)
    originals = [0 for i in range(N + 1)]
    minus = [0 for i in range(N + 1)]
    for (k, v) in c.items():
        originals[k] = v * (v-1) // 2
        minus[k] = ((v * (v-1)) - (v-1) * (v-2)) // 2
    S = sum(originals)

    ans = []
    for a in A:
        ans.append(str(S - minus[a]))
    return "\n".join(ans)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split(" ")))
    print(solve(N, A))

Submission status: Accepted

Solution code:
from collections import Counter as co
n=int(input())
l=list(map(int,input().split()))
var=co(l)
v=var.values()
ans=sum((i*(i-1))//2 for i in v)
for i in l:
    d=var[i]
    d=(d*(d-1))//2-((d-1)*(d-2))//2
    print(ans-d)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

def comb(n, r):
    if r > n:
        return 0
    r = min(r, n - r)
    if r == 0: return 1
    if r == 1: return n
    numerator = list(range(n-r+1, n+1))
    denominator = list(range(1, r+1))
    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, *a = map(int, sys.stdin.read().split())

def main():
    c = Counter(a)
    res = 0
    for v in c.values():
        res += comb(v, 2)

    for i in a:
        yield res - comb(c[i], 2) + comb(c[i]-1, 2)
        
if __name__ == "__main__":
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import Counter
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
ct = Counter(a_ls)
res = 0
for k, v in ct.items():
    res += v * (v-1) // 2
for a in a_ls:
    print(res - max(0, ct[a] - 1))

Submission status: Accepted

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

    table = collections.defaultdict(int)

    for x in A:
        table[x] += 1

    ret = 0
    for x in table:
        ret += (table[x]*(table[x]-1)) // 2
    for x in A:
        tmp = ret
        tmp -= (table[x]*(table[x]-1)) // 2
        tmp += ((table[x]-1)*(table[x]-2)) // 2
        print(tmp)


main()

Submission status: Accepted

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
l=[]
allsum=0
val=0
c=collections.Counter(A)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
for i in range(len(key)):
    l.append([key[i],values[i]])
    allsum=allsum+(values[i]*(values[i]-1))/2
for i in range(N):
    val=c[A[i]]
    print(int(allsum-(val*(val-1)/2)+((val-1)*(val-2)/2)))

Submission status: Accepted

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

dic = {}

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

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

for x in A: print(P-dic[x]+1)

Submission status: Accepted

Solution code:
from collections import defaultdict as d

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

di = d(int)
for i in arr:
	di[i] += 1
	
s = 0
for key, value in di.items():
	s += (value * (value - 1)) // 2

di2 = d(int)

for key, value in di.items():
	nw = (value * (value - 1)) // 2
	x = s - nw
	di2[key] = x + ((value - 1) * (value - 2)) // 2
	
for i in range(n):
	print(di2[arr[i]])

Submission status: Accepted

Solution code:
n=int(input())
x=[int(n) for n in input().split()]
a={}
for i in x:
    try:
        a[i]+=1 
    except:
        a[i]=1
c=0
for i in a:
    c+=((a[i]-1)*(a[i]))//2
    
for i in x:
    print(c-((a[i]-1)*(a[i]))//2+((a[i]-1)*(a[i]-2))//2)

Submission status: Accepted

Solution code:
from collections import defaultdict


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

counts = defaultdict(int)

for a in A:
    counts[a] += 1

total = 0
for num, count in counts.items():
    pattern = count * (count - 1) // 2
    total += pattern

for a in A:
    count = counts[a]
    if count == 1:
        print(total)
        continue
    prev = count * (count - 1) // 2
    after = (count - 1) * (count - 2) // 2
    delta = prev - after
    print(total - delta)

Submission status: Accepted

Solution code:
import sys
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))
from collections import defaultdict
s=0
dic=defaultdict(int)
for i in range(n):
    dic[arr[i]]+=1
for i in dic:
    s+=(dic[i]*(dic[i]-1))//2
#print(s,'s')
for i in range(n):
    a=arr[i]
    ans=s
    
    ans-=dic[a]*(dic[a]-1)//2
    if dic[a]-2>=0:
        ans+=(dic[a]-1)*(dic[a]-2)//2
    print(ans)

Submission status: Accepted

Solution code:
import collections

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

ac = collections.Counter(a)

ac_c={}
sum=0
for i,j in ac.items():
    ac_c[i]=(j*(j-1))//2
    sum+=ac_c[i]

for i in a:
    tmp=ac_c[i]-ac_c[i]*(ac[i]-2)//(ac[i])
    print(sum-tmp)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()));
lis = [0]*(N+1)
ans = [0]*(N+1)
ans_selected = [0]*(N+1)
ans_sum = 0

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

for num, i in enumerate(lis):
    ans[num] = i * (i-1) // 2
    ans_sum += i * (i-1) // 2
    if i != 0:
        ans_selected[num] = (i-1) * (i-2) // 2

for i in A:
    print(ans_sum - ans[i] + ans_selected[i])

Submission status: Accepted

Solution code:

N = int(input())
A = list(map(int,input().split()))
#%%
D = [0]*(N+1)
for a in A:
    D[a] += 1

cmb = 0
for d in D:
    cmb += d*(d-1)//2

ans = []
for i in range(N):
    d = D[A[i]]
    tmp = cmb-(d*(d-1)//2)
    tmp += (d-1)*(d-2)//2
    
    ans.append(tmp)

for an in ans:
    print(an)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
from collections import defaultdict
d = defaultdict(int)
for a in A:
  d[a] += 1

keisan = dict()

for key,value in d.items():
  keisan[key] = (value * (value-1)) // 2
res = sum(keisan.values())
# print(d,keisan)
for a in A:
  # 合計から必要なくなった部分を除去する
  val = d[a]
  
  print(res - ((val*(val-1))//2) +(((val-1)*(val-2))//2)  )

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    n = int(input())
    l = list(map(int,input().split()))
    c = Counter(l)

    
    count = 0
    for j,k in c.items():
        count += k*(k-1)//2
        
    for i in l:
        x = c[i]
        y = (x*(x-1)-(x-1)*(x-2))//2
        print(count-y)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')

N = I()
A = LMI()

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

# ad[i] := 数字iから作られるペアの数
ad = dict()
s = 0
for i, cnt in d.items():
    if cnt < 2:
        ad[i] = 0
    else:
        ad[i] = cnt * (cnt - 1) // 2
    s += ad[i]

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

Submission status: Accepted

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

n = 0

d2 = {}

for k, v in d.items():
    m = v*(v-1)//2
    d2[k] = m
    n += m

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

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

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

    max_choice = 0
    for c in nums:
        max_choice += c*(c-1)//2
    
    for k in range(N):
        x = nums[A[k]]
        print(max_choice - x*(x-1)//2 + max((x-1)*(x-2)//2,0))

    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
ans = 0
for k, v in counter.items():
    if 2 <= v:
        ans += v * (v - 1) // 2
for a in A:
    if a in counter and 2 <= counter[a]:
        v = counter[a]
        diff = v * (v - 1) // 2 - ((v- 1) * (v - 2) // 2)
        print(ans - diff)
    else:
        print(ans)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = inpl()
C = [0]*(N+1)
for i in range(N):
    C[A[i]] += 1
total = sum([ c*(c-1)//2 for c in C])
for k in range(N):
    c = C[A[k]]
    print(total - c + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N = int(input())
A = list(map(int, input().split()))
cnt = [0]*N
for i in range(N):
    cnt[A[i]-1] += 1
c_sum = 0
for i in range(N):
    c_sum += cnt[i] * (cnt[i]-1) // 2
for i in range(N):
    print(c_sum - cnt[A[i]-1] + 1)

Submission status: Accepted

Solution code:
import collections

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

c = collections.Counter(A)
ans = sum([x*(x-1)//2 for x in c.values()])

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

Submission status: Accepted

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

Submission status: Accepted

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

l1 = [0]* (n+1)

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

l2 = [0] * (n+1)

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

l3 = [0] * (n+1)

for i in range(1, n+1):
    if l1[i] > 2:
        l3[i] = (l1[i]-2) * (l1[i]-1) // 2

x = sum(l2)

l4 = [0] * (n+1)

for i in range(1, n+ 1):
    l4[i] = x - l2[i] + l3[i]


for i in range(n):
    print(l4[a[i]])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

NUM = defaultdict(int)

for a in A:
    NUM[a] += 1

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

#print(s)

ans = []
for a in A:
    r = NUM[a]
    t = s - (r - 1)
    ans.append(t)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    return ret


MOD = 10**9 + 7
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N = read_a_int()
A = read_ints()
# counterすればよくね？
A_cnt = Counter(A)
# だけどTLEになるそう
# 同じ整数の個数をカウントした数をnとするとnC2の合計がそのボールを選ぶ通りの数
# nC2とn-1C2の差はn-1

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

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

Submission status: Accepted

Solution code:
n = int(input())
a_list = [int(a) - 1 for a in input().split()]
count = [0] * n
for a in a_list:
  count[a] += 1
comb = 0
for c in count:
  comb += c * (c - 1) // 2
for a in a_list:
  c = count[a]
  print(comb - c + 1)

Submission status: Accepted

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

n = ii()
alis = li()
dp = [0] * n
for i in range(n):
    dp[alis[i] -1] += 1
dpp = [0] * n
summ = 0
for i in range(n):
    ima = dp[i] * (dp[i]-1) // 2
    summ += ima
for i in range(n):
    if dp[alis[i] -1] <=1:
        print(summ)
    else:
        mi = dp[alis[i]-1] -1 
        print(summ -mi)

Submission status: Accepted

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

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

S = 0
for n in num:
    S += n * (n - 1) // 2

ans = []
for i in range(N):
    rst = S
    p = A[i]
    m = num[p]

    rst -= m * (m - 1) // 2
    rst += (m - 1) * (m - 2) // 2
    ans.append(rst)

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
key = [0]*n
for i in range(n):
  key[a[i]-1] += 1
kake = [1]*n
ans = 0
for i in range(n):
  ans += key[i]*(key[i]-1)//2
for i in range(n):
  print(ans-(key[a[i]-1]-1))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    
    counter = defaultdict(int)
    for ai in A:
        counter[ai] += 1
    
    B = defaultdict(int)
    for ai in A:
        B[ai] = counter[ai] * (counter[ai] - 1) // 2
    
    tmp = sum(B.values())
    for ai in A:
        print(tmp - B[ai] + (counter[ai] - 1) * (counter[ai] - 2) // 2)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
d = {}

N=int(input())

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


for a in A:
    if a in d.keys():
        d[a] += 1
    else:
        d[a] = 1

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

ret1 = {}
ret2 = {}
for k in d.keys():
    ret1[k]=solve(d[k])
    ret2[k]=solve(d[k]-1)


sums=sum(ret1.values())
for  i in range(N):
    ans = sums - ret1[A[i]] + ret2[A[i]]
    print(ans)

Submission status: Accepted

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

for x in a:
    ans = s
    if cnt[x] >= 2: ans -= cnt[x]-1
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))

dict_count = {}

# 数を数える
for a in A:
  if a in dict_count.keys():
    dict_count[a] += 1
  else:
    dict_count[a] = 1

# 最大値
count_max = 0
for key, value in dict_count.items():
  count_max += value*(value-1)//2

# 答えを出力
for a in A:
  print(count_max-dict_count[a]+1)

Submission status: Accepted

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

Submission status: Accepted

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


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


# 重複組み合わせは nHr = (n + r - 1)Cn
def cmb(n, r):
    # combination
    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


def solve(v):
    if v < 2:
        return ans
    return ans - cmb(v, 2) + cmb(v - 1, 2)


N = int(input())
A = inpl()
cA = Counter(A)

ans = 0
for v in cA.values():
    ans += v * (v - 1) // 2
# print(ans)
for a in A:
    print(solve(cA[a]))

Submission status: Accepted

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

def nc2(x): return x*(x-1)//2
dic = {i+1:0 for i in range(N)}
for a in A: dic[a] += 1

tmp = 0
for i in range(N):
    tmp += nc2(dic[i+1])

ans = [0] * (N+1)
for i in range(1,N+1):
    print(tmp+nc2(dic[A[i-1]]-1)-nc2(dic[A[i-1]]))

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

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

# dic2=defaultdict(int)
ans=0
for i in dic.keys():
    ans+=dic[i]*(dic[i]-1)//2

# print(ans)
# print(dic)
for i in range(n):
    # print()
    # print(dic[a[i]]*(dic[a[i]]-1)//2)
    # print((dic[a[i]]-1)*(dic[a[i]-2])//2)
    tmp=ans-dic[a[i]]*(dic[a[i]]-1)//2+(dic[a[i]]-1)*(dic[a[i]]-2)//2
    print(tmp)

Submission status: Accepted

Solution code:
from collections import Counter

N=int(input())
A=[int(i) for i in input().split(" ")]
c=Counter(A)
c=dict(c)
base=0
for key in c:
    base+=c[key]*(c[key]-1)//2


for a in A:
    _base=base
    ca=c[a]
    if ca>1:
        _base-=ca*(ca-1)//2
        _base+=(ca-1)*(ca-2)//2
    print(_base)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

for i in range(len(A)):
    print(s - count[A[i]] + 1)

Submission status: Accepted

Solution code:
from collections import Counter

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

ct = Counter(A)
d = dict()
for k, v in ct.items():
    d[k] = v * (v - 1) // 2

s = sum(d.values())

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

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    X = [0] * (N + 1)
    
    for a in A:
        X[a] += 1
    s = 0
    for x in X:
        s += x*(x-1)//2

    for a in A:
        print(s - X[a] + 1)



    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
d={}
for a in A:
    if a not in d:
        d[a]=1
    else:
        d[a]+=1
ans=0
for k in d.keys():
    e=d[k]
    ans+=e*(e-1)//2
for a in A:
    keep=ans
    e=d[a]
    temp=e*(e-1)//2
    ans-=temp
    ans+=(e-1)*(e-2)//2
    print(ans)
    ans=keep

Submission status: Accepted

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

ans = []
for a in A:
    ans.append(al - ctr[a] + 1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
comb = [0] * (n + 1)
cnt = Counter(a)

for key in cnt.keys():
    comb[key] = cnt[key] * (cnt[key] - 1) // 2
total = sum(comb)

for item in a:
    if comb[item] <= 1:
        diff = comb[item]
    else:
        diff = comb[item] - (comb[item] * (cnt[item] - 2)) // cnt[item]
    print(total - diff)

Submission status: Accepted

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

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

L2 = []
for i in L:
    L2.append(L[i]*(L[i]-1)/2)
    
res = sum(L2)
for i in A:
    print(int(res - L[i] + 1))

Submission status: Accepted

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

def cmb(m, n):
    if m - n < n:
        n = m - n
    if n == 0:
        return 1
    if n == 1:
        return m
    
    numerator = [m - n + k + 1 for k in range(n)]
    denominator = [k + 1 for k in range(n)]

    for p in range(2, n+1):
        pivot = denominator[p-1]
        if pivot > 1:
            offset = (m-n) % p
            for k in range(p-1, n, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    
    result = 1
    for k in range(n):
        if numerator[k] > 1:
            result *= int(numerator[k])
            
            # mod(10**9+7)
            # result = result % (10**9+7)

    return result


Dict = {x:0 for x in range(n+1)}
for a in A:
    Dict[a] += 1

Non_minus = [0 for _ in range(n+1)]
one_minus = [0 for _ in range(n+1)]

for i in range(1, n+1):
    if Dict[i] <= 1:
        Non_minus[i] = 0
        one_minus[i] = 0
    elif Dict[i] == 2:
        Non_minus[i] = 1
        one_minus[i] = 0
    else:
        Non_minus[i] = cmb(Dict[i],2)
        one_minus[i] = cmb(Dict[i]-1, 2)

total_non = sum(Non_minus)

# print(Non_minus)
# print(one_minus)

for i in range(n):
    ans = total_non - Non_minus[A[i]] + one_minus[A[i]]
    print(ans)

Submission status: Accepted

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

cnt = Counter(a)

ans = 0

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

for k in a:
    print(ans - cnt[k] + 1)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
import math
def ncr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
import collections
d=collections.defaultdict(int)

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

total=0
for i in d.values():
    if i>=2:
        total+=ncr(i,2)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import itertools
import bisect
from operator import itemgetter
 
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
def combi(n, r):
  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 = I()
a = IL()

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

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

for i in a:
  n = dic[i]
  print(ans - n*(n-1)//2 + (n-1)*(n-2)//2 )

Submission status: Accepted

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

li = [0]*(n+1)

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

li2 = [[0]*2 for _ in range(n+1)]

for i in range(n+1):
    for j in range(2):
        if j == 0:
            li2[i][j] = li[i] * (li[i] - 1) // 2
        else:
            li2[i][j] = max((li[i] - 1) * (li[i] - 2) // 2, 0)

sum1 = 0
for i in range(n+1):
    sum1 += li2[i][0]

sum2 = [0]*(n+1)

for i in range(n+1):
    sum2[i] = sum1 - li2[i][0] + li2[i][1]

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
ans = 0
t = (n - 1) * (n - 2) // 2
for k, v in c.items():
    ans += v * (v - 1) // 2
for y in a:
    x = c[y]
    print(ans - x * (x - 1) // 2 + (x - 1) * (x - 2) // 2)

Submission status: Accepted

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left #bisect_left(list, value)
#from fractions import gcd
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input():
    return sys.stdin.readline()[:-1]
def pri(x):
    if type(x) is list:
        print('\n'.join(map(str, x)))
    else:
        print(x)

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

#sA = list(sorted(A))
c = Counter(A)
cnt = 0
for ci in c.values():
    cnt += ci*(ci-1)//2

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

Submission status: Accepted

Solution code:

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


x=[0]*N
y=[0]*N
z=[0]*N
for i in range(N):
     j=A[i]
     x[j-1] += 1

for i in range(N):
    j=i
    y[i]=(x[j]*(x[j]-1))//2
    if x[j]==0:
        z[i]=0
    else:
        z[i]=((x[j]-2)*(x[j]-1))//2

yy=sum(y)
zz=sum(z)


for i in range(N):
    j=A[i]
    print(yy-y[j-1]+z[j-1])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
for a in A:
    d[a] += 1
#print(d)

total = 0
for a in d:
    total += d[a] * (d[a] - 1) // 2
#print(total)

for i in range(N):
    a = A[i]
    print(total - (d[a] - 1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
n = int(input())
a = [int(x) for x in input().split()]
d = defaultdict(int)
for v in a:
    d[v] += 1
r = 0
for v in d:
    r += d[v] * (d[v] - 1) // 2
for v in a:
    if d[v] == 1:
        print(r)
    else:
        r1 = r - d[v] * (d[v] - 1) // 2 + (d[v] - 2) * (d[v] - 1) // 2
        print(r1)