[SDOI2016]生成魔咒

题目描述

魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字符 $1,2$ 拼凑起来形成一个魔咒串 $[1,2]$。 一个魔咒串 $S$ 的非空字串被称为魔咒串 $S$ 的生成魔咒。 例如 $S=[1,2,1]$ 时,它的生成魔咒有 $[1],[2],[1,2],[2,1],[1,2,1]$ 五种。$S=[1,1,1]$ 时,它的生成魔咒有 $[1],[1,1],[1,1,1]$ 三种,最初 S 为空串。 共进行 $n$ 次操作,每次操作是在 $S$ 的结尾加入一个魔咒字符。每次操作后都需要求出,当前的魔咒串 $S$ 共有多少种生成魔咒。

输入输出格式

输入格式


第一行一个整数 $n$。 第二行 $n$ 个数,第 $i$ 个数表示第 $i$ 次操作加入的魔咒字符 $x_i$。

输出格式


输出 $n$ 行,每行一个数。 第 $i$ 行的数表示第 $i$ 次操作后 $S$ 的生成魔咒数量

输入输出样例

输入样例 #1

7
1 2 3 3 3 1 2

输出样例 #1

1
3
6
9
12
17
22

说明

#### 数据规模与约定 对于 $10\%$ 的数据,保证 $1 \le n \le 10$; 对于 $30\%$ 的数据,保证 $1 \le n \le 100$; 对于 $60\%$ 的数据,保证 $1 \le n \le 10^3$; 对于 $100\%$ 的数据,保证 $1 \le n \le 10^5$,$1 \leq x_i \leq 10^9$。