Description

伟大的小蝙狐自然会许多的魔咒，但很可惜在这个世界观下每次施法需要念出咒语，也就是所谓的施法前摇。

就像普通的话语一样，咒语也是由许多字符组成，

伟大的魔法师们为了减少施法前摇，所以将这些字符用数字进行表示。

例如可以将字符 $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 会产生多少种魔法。

$\tiny好的法师应该学会近战，而不是在后边念咒语——大魔导师小狐芦$

Input

第一行一个整数 n。

第二行 n 个数，第$i$个数表示第$i$次操作加入的字符。

Output

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

Samples

6
1 1 4 5 1 4

1
2
5
9
13
17

Limitation

对于 100% 的数据，$1 \leqslant n \leqslant 100000$。用来表示字符的数字 $x$ 满足 $1\leqslant x\leqslant 10^9$。