D - Banned K Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

ボールが N 個あり、 i 番目のボールには整数 A_i が書かれています。
k=1,2,...,N に対して以下の問題を解いて、答えをそれぞれ出力してください。

  • k 番目のボールを除いた N-1 個のボールから、書かれている整数が等しいような異なる 2 つのボールを選び出す方法の数を求めてください。選ぶ順序は考慮しません。

制約

  • 3 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq N
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。 

N
A_1 A_2 ... A_N

出力

k=1,2,...,N に対する答えを順番に一行ずつ出力せよ。

入力例 1

5
1 1 2 1 2

出力例 1

2
2
3
2
3

例えば k=1 のとき、残りのボールに書かれている数はそれぞれ {1,2,1,2} です。
この中から書かれている数が等しいような異なる 2 つのボールを選び出す方法は 2 通りあります。
したがって、 k=1 に対する問題の答えは 2 です。

入力例 2

4
1 2 3 4

出力例 2

0
0
0
0

どの 2 つのボールを選び出しても、書かれている数は等しくありません。

入力例 3

5
3 3 3 3 3

出力例 3

6
6
6
6
6

どの 2 つのボールを選び出しても、書かれている数が等しいです。

入力例 4

8
1 2 1 4 2 1 4 1

出力例 4

5
7
5
7
7
5
7
5

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