题目描述

译自 ROIR 2020 Day1 T3. Борьба с рутиной

判断员工业绩的一个重要因素就是处理日常事务的能力。

我们考虑员工连续 $n$ 天的工作情况，第 $i$ 天执行的工作为 $a_i$。

为了评估员工的工作业绩，使用以下方法：

选定一个整数 $d$，考虑所有连续 $d$ 天的日期段，对于每一段这样的日子，我们统计员工完成的不同工作的种类数。

记 $S_d$ 表示每一段这样连续 $d$ 天的日期段完成的不同种类工作数之和。

现在需要你来统计出 $S_{1 \sim n}$ 的值。

输入格式

输入共两行:

第一行为一个整数 $n$，表示工作的总天数。

第二行 $n$ 个整数，表示每天所做的工作种类编号。

输出格式

输出共 $n$ 个数，为 $S_{1 \sim n}$。

样例 1

输入

5
1 3 2 1 2

输出

5 8 8 6 3

$S_1$:

日期段	所有工种	不同的工种的数量
1-1	1	1
2-2	3
3-3	2
4-4	1
5-5	2

所以 $S_1 = 1 + 1 + 1 + 1 + 1 = 5$。

$S_2$:

日期段	所有工种	不同的工种的数量
1-2	1, 3	2
2-3	3, 2
3-4	2, 1
4-5	1, 2

所以 $S_2 = 2 + 2 + 2 + 2 = 8$。

$S_3$:

日期段	所有工种	不同的工种的数量
1-3	1, 3, 2	3
2-4	3, 2, 1
3-5	2, 1, 2	2

所以 $S_3 = 3 + 3 + 2 = 8$。

$S_4$:

日期段	所有工种	不同的工种的数量
1-4	1, 3, 2, 1	3
2-5	3, 2, 1, 2

所以 $S_4 = 3 + 3 = 6$。

$S_5$:

日期段	所有工种	不同的工种的数量
1-5	1, 3, 2, 1, 2	3

所以 $S_5 = 3$。

样例 2

输入

3
10 10 10

输出

3 2 1

数据范围与提示

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 10^9$。

任务编号	特殊限制	分值
1	$1 \leq n \leq 50$，$1 \leq a_i \leq 50$	$12$
2	$1 \leq n \leq 50$，$1 \leq a_i \leq 10^9$	$10$
3	$1 \leq n \leq 500$，$1 \leq a_i \leq 10^9$
4	$1 \leq n \leq 5000$，$1 \leq a_i \leq 5000$	$12$
5	$1 \leq n \leq 5000$，$1 \leq a_i \leq 10^9$	$10$
6	$1 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 50$	$16$
7	无特殊限制	$30$