#8764. 小韩前缀询问 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wind_Rises

题目描述

小韩拿到了一个数组,他有若干次询问,每次询问一个前缀内有多少对相同的数。你能帮帮他吗?

如果存在 ,,且 = ,那么(,)就是一对相同的数对。只要下标不同,就是不同的数对。

输入格式

第一行输入一个正整数 ,代表数组大小。

第二行输入 个正整数 ;,代表小红拿到的数组。

输出格式

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

样例

样例输入

复制6
2 3 3 3 1 2

样例输出

复制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对相同的数。

数据范围与提示