小韩拿到了一个数组,他有若干次询问,每次询问一个前缀内有多少对相同的数。你能帮帮他吗?
如果存在 ,,,且 = ,那么(,)就是一对相同的数对。只要下标不同,就是不同的数对。
第一行输入一个正整数 ,代表数组大小。
第二行输入 个正整数 ;,代表小红拿到的数组。
输出 个整数,第 个整数代表前缀 [,], 内有多少对相同的数。
样例输入
复制6 2 3 3 3 1 2
6 2 3 3 3 1 2
样例输出
复制0 0 1 3 3 4
0 0 1 3 3 4
样例解释
对于前缀[2],没有相同的数。 对于前缀[2,3],没有相同的数。 对于前缀[2,3,31,有1对相同的数。 对于前缀[2,3,3,31,有3对相同的数。 对于前缀[2,3,3,3,1],有3对相同的数。 对于前缀[2,3,3,3,1,2],有4对相同的数。