P15696 [2018 KAIST RUN Spring] QueryreuQ

如果一个字符串正读和反读都相同，则称其为**回文串**。例如，像 “a”、“aa”、“appa”、“queryreuq” 这样的字符串都是回文串。 对于一个给定的初始为空字符串 $S$，你需要处理以下两种操作： 1. 在 $S$ 的末尾添加一个小写字母。 2. 删除 $S$ 末尾的一个字符。 在处理完每次操作后，你需要计算 $S$ 中**回文子串**的数量。对于字符串 $S$ 和整数 $i$, $j$（$1 \le i \le j \le |S|$），$S[i, j]$ 表示 $S$ 中从第 $i$ 个到第 $j$ 个字符构成的子串。你需要输出满足 $S[i, j]$ 是回文串的整数对 $(i, j)$ 的数量。

输入包含两行。 第一行给出一个整数 $Q$，表示操作的数量。 第二行给出一个长度为 $Q$ 的字符串来描述所有操作。第 $i$ 个字符 $K_i$ 表示第 $i$ 次操作。$K_i$ 是 ‘-’ 或小写字母（‘a’, ‘b’, …, ‘z’）（不包含引号）。 如果字符是 ‘-’，则你应该删除 $S$ 末尾的一个字符。如果字符是小写字母，则你应该将字符 $K_i$ 添加到 $S$ 的末尾。 保证每次操作后 $S$ 的长度始终为正数。

在第一行输出 $Q$ 个由空格分隔的整数。第 $i$ 个整数应该是第 $i$ 次操作后的答案。

### 数据范围 - $1 \le Q \le 10,000$