Banned K

题目描述

我们有 $N$ 个球。第 $i$ 个球上写着一个整数 $A_i$。
对于每个 $k=1, 2, ..., N$，解决以下问题并输出答案。

在去掉第 $k$ 个球后的 $N-1$ 个球中，计算有多少种方法从中选择两个不同的球（不考虑顺序），使得它们上面写的整数相等。

输入格式

输入从标准输入按以下格式给出： $N$ $A_1$ $A_2$ $...$ $A_N$

输出格式

对于每个 $k=1,2,...,N$，打印一行包含答案。

5
1 1 2 1 2

2
2
3
2
3

4
1 2 3 4

0
0
0
0

5
3 3 3 3 3

6
6
6
6
6

8
1 2 1 4 2 1 4 1

5
7
5
7
7
5
7
5

提示

$3 \leq N \leq 2 \times 10^5$ $1 \leq A_i \leq N$ 输入中的所有数值均为整数。例如考虑 $k=1$ 的情况。剩下的球上写的数字是 $1,2,1,2$。
在这些球中，有两种方法选择两个不同的球使得它们上面写的整数相等。
因此，$k=1$ 的答案是 $2$。
没有两个球上写着相同的数字。
任意两球上写着相同的数字。

标签: AtCoder|abc159D

来源

AtCoder|abc159D