Background

$遇见彩虹，吃定彩虹！$

$给你N颗不同颜色的彩虹糖，第i个彩虹糖的颜色是Ai$

$你有多少种方式可以拿到两颗颜色一样的彩虹糖呢？$ $(每颗彩虹糖都是独一无二的哦)$

$这个问题有点简单是吧$

$没关系，杰瑞来捣个乱$

$第i天他会将第Ai颗糖果藏起来$

$那你现在还可算第i天有多少种方式拿到相同颜色的彩虹糖吗？$

Description

$给你N颗不同颜色的彩虹糖$

$请你对于1-N天的每一天，计算有多少种方法拿到颜色相同的两颗糖？$

$注意第i天 杰瑞会把第Ai颗糖果藏起来哦$

Format

Input

$共两行$ $第一行包含一个整数$ $N$ $(3 \leq N \leq 2 \times 10^{5})$ $第二行包含$N$个整数$，$以空格间隔$ $A_{1}$ $A_{2}$ $...$ $A_{N}$ $(1 \leq A_{i} \leq N)$ .

Output

$共$N$行$ $每行包含一个整数，表示第$i$周小$X$能够选择的不同借书方案数$

Samples

5
1 1 2 1 2

2
2
3
2
3

$第一天，A1被藏起来了，拿到相同糖果的两种方式为$

$（A3,A5）（A2,A4）$

$第二天，A2被藏起来了，拿到相同糖果的两种方式为$

$（A1,A3）（A3,A5）$

$第三天，A3被藏起来了，三种方式为$

$（A1,A2）（A1,A3）（A2,A3）$

$以此类推$

Limitation

1s, 1024KiB for each test case.