Magic Factor

吸血鬼病毒（ヴァンパイアウィルス）由许多因子组成，这些因子可以用数字表示。

例如可以将因子1,2 1, 2 1,2、拼凑起来形成一个因子串[1,2][1, 2][1,2]。

一个因子串SSS的非空子串（参见高一数学课本 —— 非空子集）被称为因子串SSS的生成因子。

例如S=[1,1,1]时，它的生成因子有三种，分别是S = [1, 1, 1] 时，它的生成因子有三种，分别是S=[1,1,1]时，它的生成因子有三种，分别是[1] / [1, 1] / [1, 1, 1]。当然，最初。当然，最初。当然，最初S$为空串。

共有TTT次操作，每次操作在因子串的结尾加入一个因子。

需要求出，当前的因子串共有多少种生成因子。

Input

第一行一个整数TTT。

第二行TTT个数，第iii个数表示第iii次操作加入的因子。

Output

输出TTT行，每行一个数。

第iii行表示第iii次操作后的生成因子的数量。

Sample Input 1

6
1 2 3 3 3 1

Sample Output 1

1
3
6
9
12
17

参考GPT和自己的思路：

这个问题可以用动态规划来解决。

令dp[i]表示以第i个因子结尾的生成因子的个数，则有以下转移方程：

• 若第i个因子与第i-1个因子相同，则dp[i] = dp[i-1] + i-1，即以第i个因子结尾的生成因子包含以前一个因子结尾的所有生成因子，并且每个生成因子都可以新增一个因子与第i个因子组成新的生成因子。
• 若第i个因子与第i-1个因子不同，则dp[i] = dp[i-1] + i，即以第i个因子结尾的生成因子包含以前所有因子结尾的生成因子，并且每个生成因子都可以新增一个因子与第i个因子组成新的生成因子。

最终答案就是dp数组中所有元素之和。

时间复杂度为O(T)。

代码示例如下：