题目描述

沈睿拿到了一个数组，他有若干次询问，每次询问一个前缀内有多少对相同的数。你能帮帮他吗？ 如果存在i,j,使得 $1≤i$<j≤n，且a~i~=a~j~，那么（a~i~，a~j~）就是一对相同的数对。只要下标不同，就是不同的数对。

输入格式

第一行输入一个整数 $n$，代表数组大小 第二行输入 $n$ 个整数a~i~，代表沈睿拿到的数组 $1<=n<=10$^$5$^,$1$<=a~i~<=$10^9$^

输出格式

输出 $n$ 个整数 第 $i$ 个整数代表前缀[$1$,i]内有多少对相同的数

样例

样例输入 1

6
2 3 3 3 1 2

样例输出 1

0 0 1 3 3 4

提示

对于前缀 [$2$]，没有相同的数。 对于前缀 [$2$,$3$]，没有相同的数。 对于前缀 [$2$,$3$,$3$]，有 $1$ 对相同的数。 对于前缀 [$2$,$3$,$3$,$3$]，有 $3$ 对相同的数。 对于前缀 [$2$,$3$,$3$,$3$,$1$]，有 $3$ 对相同的数。 对于前缀 [$2$,$3$,$3$,$3$,$1$,$2$]，有 $4$ 对相同的数。