#349. 4516. [Sdoi2016]生成魔咒

4516. [Sdoi2016]生成魔咒

[SDOI2016] 生成魔咒

题目描述

魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字符 1,21,2 拼凑起来形成一个魔咒串 [1,2][1,2]

一个魔咒串 SS 的非空字串被称为魔咒串 SS 的生成魔咒。

例如 S=[1,2,1]S=[1,2,1] 时,它的生成魔咒有 [1],[2],[1,2],[2,1],[1,2,1][1],[2],[1,2],[2,1],[1,2,1] 五种。S=[1,1,1]S=[1,1,1] 时,它的生成魔咒有 [1],[1,1],[1,1,1][1],[1,1],[1,1,1] 三种,最初 S 为空串。

共进行 nn 次操作,每次操作是在 SS 的结尾加入一个魔咒字符。每次操作后都需要求出,当前的魔咒串 SS 共有多少种生成魔咒。

输入格式

第一行一个整数 nn

第二行 nn 个数,第 ii 个数表示第 ii 次操作加入的魔咒字符 xix_i

输出格式

输出 nn 行,每行一个数。 第 ii 行的数表示第 ii 次操作后 SS 的生成魔咒数量

样例 #1

样例输入 #1

7
1 2 3 3 3 1 2

样例输出 #1

1
3
6
9
12
17
22

提示

数据规模与约定

对于 10%10\% 的数据,保证 1n101 \le n \le 10; 对于 30%30\% 的数据,保证 1n1001 \le n \le 100; 对于 60%60\% 的数据,保证 1n1031 \le n \le 10^3; 对于 100%100\% 的数据,保证 1n1051 \le n \le 10^51xi1091 \leq x_i \leq 10^9