{"raw_statement":[{"iden":"statement","content":"**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day1 T3.** ***[Борьба с рутиной\n](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day1.pdf)，译者ShineEternal***\n\n判断员工业绩的一个重要因素就是处理日常事务的能力。\n\n我们考虑员工连续 $n$ 天的工作情况，第 $i$ 天执行的工作为 $a_i$。\n\n为了评估员工的工作业绩，使用以下方法：\n\n选定一个整数 $d$，考虑所有 连续 $d$ 天的日期段，对于每一段这样的日子，我们统计员工完成的不同工作的种类数。\n\n记 $S_d$ 表示每一段这样连续 $d$ 天的日期段完成的不同种类工作数之和。\n\n现在需要你来统计出 $S_{1\\sim n}$ 的值。"},{"iden":"input","content":"输入共两行:\n\n第一行为一个整数 $n$，表示工作的总天数。\n\n第二行 $n$ 个整数，表示每天所做的工作种类编号。"},{"iden":"output","content":"输出共 $n$ 个数，为 $S_{1\\sim n}$。"},{"iden":"note","content":"#### 【样例 1 解释】\n- $S_1$:\n\n| 日期段 | 所有工种 | 不同的工种的数量 |\n| :----: | :------: | :--------------: |\n| $1-1$  |   $1$    |       $1$        |\n| $2-2$  |   $3$    |       $1$        |\n| $3-3$  |   $2$    |       $1$        |\n| $4-4$  |   $1$    |       $1$        |\n| $5-5$  |   $2$    |       $1$        |\n\n\n\n所以 $S_1=1+1+1+1+1=5$。\n\n- $S_2$:\n\n|日期段|所有工种|不同的工种的数量|\n|:-:|:-:|:-:|\n|$1-2$|$1,3$|$2$|\n|$2-3$|$3,2$|$2$|\n|$3-4$|$2,1$|$2$|\n|$4-5$|$1,2$|$2$|\n\n所以 $S_2=2+2+2+2=8$。\n\n- $S_3$:\n\n|日期段|所有工种|不同的工种的数量|\n|:-:|:-:|:-:|\n|$1-3$|$1,3,2$|$3$|\n|$2-4$|$3,2,1$|$3$|\n|$3-5$|$2,1,2$|$2$|\n\n所以 $S_3=3+3+2=8$。\n\n- $S_4$:\n\n|日期段|所有工种|不同的工种的数量|\n|:-:|:-:|:-:|\n|$1-4$|$1,3,2,1$|$3$|\n|$2-5$|$3,2,1,2$|$3$|\n\n所以 $S_4=3+3=6$。\n\n- $S_5$:\n\n|日期段|所有工种|不同的工种的数量|\n|:-:|:-:|:-:|\n|$1-5$|$1,3,2,1,2$|$3$|\n\n所以 $S_5=3$。\n\n#### 【数据范围】\n对于 $100\\%$ 的数据， $1\\leq n\\leq 2\\times 10^5$，$1\\leq a_i\\leq 10^9$。\n\n|任务编号|特殊限制|分值|\n|:-:|:-:|:-:|\n|$1$|$1\\leq n \\leq 50, 1 \\leq a_i \\leq 50$|$12$|\n|$2$|$1\\leq n \\leq 50, 1 \\leq a_i \\leq 10^9$|$10$|\n|$3$|$1\\leq n \\leq 500, 1 \\leq a_i \\leq 10^9$|$10$|\n|$4$|$1\\leq n \\leq 5000, 1 \\leq a_i \\leq 5000$|$12$|\n|$5$|$1\\leq n \\leq 5000, 1 \\leq a_i \\leq 10^9$|$10$|\n|$6$|$1\\leq n \\leq 2\\times 10^5, 1 \\leq a_i \\leq 50$|$16$|\n|$7$|无特殊限制|$30$|"}],"translated_statement":null,"sample_group":[["5\n1 3 2 1 2","5 8 8 6 3"],["3\n10 10 10","3 2 1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}