P9785 [ROIR 2020] 对常规的斗争 (Day1)

**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day1 T3.** ***[Борьба с рутиной ](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day1.pdf)，译者ShineEternal*** 判断员工业绩的一个重要因素就是处理日常事务的能力。 我们考虑员工连续 $n$ 天的工作情况，第 $i$ 天执行的工作为 $a_i$。 为了评估员工的工作业绩，使用以下方法： 选定一个整数 $d$，考虑所有 连续 $d$ 天的日期段，对于每一段这样的日子，我们统计员工完成的不同工作的种类数。 记 $S_d$ 表示每一段这样连续 $d$ 天的日期段完成的不同种类工作数之和。 现在需要你来统计出 $S_{1\sim n}$ 的值。

输入共两行: 第一行为一个整数 $n$，表示工作的总天数。 第二行 $n$ 个整数，表示每天所做的工作种类编号。

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

#### 【样例 1 解释】 - $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$。 #### 【数据范围】 对于 $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$|$10$| |$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$|