Description

有 N 只球，第 i 只球上有一个数字 Ai ，

对于每一个 k(1≤k≤N)

询问：去掉第 k 只球后，在剩余的球中能找出几对数字相同的球。

Format

Input

第一行给出N

第二行给出这N个球上标的数字化

3≤N≤2×10^5

1≤Ai≤N

Output

依次输出当分别去掉第1个，第2个，第3个....第N个球后，在在剩余的球中能找出几对数字相同的球。

Samples

5
1 1 2 1 2

2
2
3
2
3