提高员工工作效率的重要方法之一，是减少工作内容的单调重复。下面建立一个数学模型，用来描述员工在公司中完成任务类型的多样性。

考虑某位员工连续 $n$ 个工作日的工作情况。假设每天该员工恰好完成一种类型的任务，用整数 $a_i$ 表示第 $i$ 天完成的任务类型。

为了评估工作的单调程度，定义如下指标。固定一个整数 $d$，考虑所有长度为 $d$ 的连续工作日区间。对每个这样的区间，统计其中出现过多少种不同的任务类型，并将这些数量相加。所得值记为 $S_d$，称为 $d$-多样性。$d$-多样性越高，表示员工在长度为 $d$ 的时间段中接触到的任务类型越多。

员工的多样性档案定义为数组：

请编写程序，给定任务类型序列 $a_1,a_2,\ldots,a_n$，计算该员工的多样性档案。

输入格式

第一行包含整数 $n$，表示需要分析的连续工作日数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每天完成的任务类型。

输出格式

输出 $n$ 个整数：

子任务

样例 1

样例输入

5
1 3 2 1 2

样例输出

5 8 8 6 3

样例 2

样例输入

3
10 10 10

样例输出

3 2 1

样例解释

以样例 1 为例：

• $S_1=1+1+1+1+1=5$；
• 长度为 $2$ 的所有区间分别为 $[1,3]$、$[3,2]$、$[2,1]$、$[1,2]$，每个区间中都有 $2$ 种不同任务，因此 $S_2=8$；
• 长度为 $3$ 的区间中，不同任务数分别为 $3,3,2$，因此 $S_3=8$；
• 长度为 $4$ 的区间中，不同任务数分别为 $3,3$，因此 $S_4=6$；
• 长度为 $5$ 的唯一一个区间中有 $3$ 种不同任务，因此 $S_5=3$。