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.

Examples

Input

5
1 1 2 1 2


Output

2
2
3
2
3


Input

4
1 2 3 4


Output

0
0
0
0


Input

5
3 3 3 3 3


Output

6
6
6
6
6


Input

8
1 2 1 4 2 1 4 1


Output

5
7
5
7
7
5
7
5
import copy

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

B = copy.deepcopy(A)
B.sort()

#print A,B

C = [-1 for i in range(N)]
D = [-1 for i in range(N)]

n = -1
p = -1
for i in range(N):
    if n != B[i]:
        p+=1
        if (p > 0 and D[p-1] == 1): p-=1
        C[p] = B[i]
        D[p] = 1
        n = B[i]
    else:
        D[p] += 1
if D[p] == 1:
    C[p] = -1
    D[p] = -1
    p -= 1

#print C, D
#print "p=",p
p += 1

E = [-1 for i in range(p)]
F = [-1 for i in range(p)]

sum = 0
for i in range(p):
    E[i] = D[i]*(D[i]-1)/2
    sum += E[i]
    F[i] = E[i] - (D[i]-1)*(D[i]-2)/2

#print "C=",C
#print E, F, sum

def binsearch(k, s, e):
    #print k,s,e
    if s == e or s + 1 == e:
        if C[s] == k:
            return s
        elif C[e] == k:
            return e
        else:
            return -1
    elif (C[(s+e)/2] < k):
        return binsearch(k, (s+e)/2, e)
    else:
        return binsearch(k, s, (s+e)/2)

for i in range(N):
    pos = binsearch(A[i], 0, p-1)
    #print "pos = ", pos
    if pos >= 0:
        print sum - F[pos]
    else:
        print sum
