Description

Farmer John’s United Cows of Farmer John (UCFJ) are competing in the annual hoofball tournament. UCFJ’s team of $N(1 \le N \le 7500)$ cows narrowly defeated Farmer Nhoj’s team and won the gold medal.

The cows have lined up for the award ceremony. They want FJ to take $\dfrac{N(N+1)}{2}$ group photos, one for every contiguous subsegment of the team.

However, as the coach, FJ is very picky about how the cows line up. In particular, he refuses to take a photo of a subsegment unless it forms a palindrome, meaning that for every positive integer $i$ not exceeding the length of the subsegment, the breed of the $i$-th cow from the left end must be the same as the breed of the $i$-th cow from the right end. Each cow’s breed is either Guernsey or Holstein.

For each of the team’s $\dfrac{N(N+1)}{2}$ contiguous subsegments, compute the minimum number of swaps needed to rearrange that subsegment into a palindrome (or $-1$ if it is impossible). A single swap consists of taking two adjacent cows in the subsequence and swapping them. Output the sum of these values over all subsegments.

Note that the number of swaps needed for each contiguous subsegment is computed independently (the cows return to their original positions between photos).

Input Format

Input the team as a string of length $N$ consisting of the characters $\texttt{G}$ and $\texttt{H}$.

Output Format

Output the sum of the quantities described above over all $\dfrac{N(N+1)}{2}$ contiguous subsegments.

GHHGGHHGH

12

Hint

Sample 1 Explanation

The first four contiguous subsegments are $\texttt{G}$, $\texttt{GH}$, $\texttt{GHH}$, and $\texttt{GHHG}$. $\texttt{G}$ and $\texttt{GHHG}$ are already palindromes, so their contribution to the total is $0$. $\texttt{GHH}$ can be rearranged into a palindrome using one swap, so its contribution to the total is $1$. $\texttt{GH}$ cannot be rearranged into a palindrome using any number of swaps, so its contribution to the total is $-1$.

$\texttt{HHGG}$ is another contiguous subsegment that contributes to the total. This subsegment can be rearranged into a palindrome using two swaps.

Test Case Properties

Besides the sample, there are fifteen test cases, one each with $N \in \{ 100,200,500,1000,2000,5000,5000,5000,5000,5000,7500,7500,7500,7500,7500\}$.

Translated by ChatGPT 5