题目描述

译自 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$|$1$| |$3-3$|$2$|$1$| |$4-4$|$1$|$1$| |$5-5$|$2$|$1$|

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

• $S_2$:

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

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

• $S_3$:

|日期段|所有工种|不同的工种的数量| |:-:|:-:|:-:|:-:| |$1-3$|$1,3,2$|$3$| |$2-4$|$3,2,1$|$3$| |$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$|$3$|

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

• $S_5$:

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

所以 $S_5=3$。

3
10 10 10

3 2 1

数据范围与提示

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