P15696 [2018 KAIST RUN Spring] QueryreuQ

A string is **palindrome**, if the string reads the same backward and forward. For example, strings like “a”, “aa”, “appa”, “queryreuq” are all palindromes. For given empty string $S$, you should process following two queries: 1. Add a lower case alphabet at the back of $S$. 2. Remove a character at the back of $S$. After processing a query, you should count the number of **palindrome substring** in $S$. For string $S$ and integers $i$, $j$ ($1 \le i \le j \le |S|$), $S[i, j]$ represents a substring from $i$th to $j$th character of $S$. You should print out the number of integer pairs $(i, j)$ where $S[i, j]$ is palindrome.

Input consists of two lines. In the first line, $Q$, the number of queries is given. In the second line, the query is given as string of length $Q$. $i$th character $K_i$ denotes the $i$th query. $K_i$ is ‘-’ or lower case alphabet (‘a’, ‘b’, …, ‘z’) (without quotes). If the character is ‘-’, you should remove a character at the back of $S$. If the character is lower case alphabet, you should add a character $K_i$ at the back of $S$. It is guaranteed that length of $S$ is always positive after the query.

Print out $Q$ space-separated integers in the first line. $i$-th integer should be the answer of the $i$th query.

### Constraints - $1 \le Q \le 10,000$