题目描述

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

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

我们考虑员工连续 $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

数据范围与提示

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