思路: 数学优化 + 哈希表

暴力思路：对于一个位置i，我们考虑往前找所有s[i] == s[j] 的位置j。那么[j+1,i-1]这一段的任意一个字符都可以被选择，也就是j对i的答案贡献就是j - i - 1。也就是找到所有的j，去求和。

那么位置i的答案是:

发现第一个求和式的内容(i - 1) 与 j无关:

题目内容

小美定义一个字符串的权值为:其长度为3的回文子序列数量。例如，"$abca$"的权值为$2$，因为包含 两个回文子序列"$aba$"和"$aca$"。

现在给定一个仅包含小写字母的字符串，小美希望你输出该字符串每个前缀的权值。

输入描述

第一行输入一个正整数$n$，代表字符串长度。

第二行输入一个长度为$n$的、仅包含小写字母的字符 串。 $1≤n≤10^5$

输出描述

输出$n$个整数，分别代表长度为$1$到$n$每个前缀的权值。

样例1

输入

6
aaaaba

输出

0 0 1 4 4 14

说明

对于"$aaaaba$"，共有$10$个"$aaa$"子序列和$4$个"$aba$"子序列，因此权值是$14$。