题目描述

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 $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$ 次操作加入的魔咒字符。

输出格式

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

样例

输入

7
1 2 3 3 3 1 2

输出

1
3
6
9
12
17
22

数据范围与提示

• 对于 $10\%$ 的数据，$1 \leq n \leq 10$；
• 对于 $30\%$ 的数据，$1 \leq n \leq 100$；
• 对于 $60\%$ 的数据，$1 \leq n \leq 1000$；
• 对于 $100\%$ 的数据，$1 \leq n \leq 100000$。

用来表示魔咒字符的数字 $x$ 满足 $1 \leq x \leq 10 ^ 9$。