题目描述

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

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

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

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

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

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

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

输入格式

输入共两行:

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

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

输出格式

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

5
1 3 2 1 2

5 8 8 6 3

3
10 10 10

3 2 1

提示

【样例 1 解释】

• $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$。

【数据范围】

对于 $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$