A6426 | 「USACO 2022.12 Platinum」Palindromes

**题目来自 [USACO 2022 December Contest, Platinum](http://usaco.org/index.php?page=dec22results) Problem 3. [Palindromes](http://usaco.org/index.php?page=viewproblem2&cpid=1262)**

农夫约翰合牛国（The United Cows of Farmer John，UCFJ）正在参加一年一度的蹄球锦标赛！UCFJ 队的 $N$（$1\le N\le 7500$）头奶牛以微弱优势击败了 Farmer Nhoj 的队伍，赢得了蹄球比赛的金牌。

奶牛们已经为颁奖典礼排好了队。她们希望 FJ 拍摄 $\frac{N(N+1)}{2}$ 张合影，为队伍的每个连续子段拍摄一张。

然而，FJ，作为球队的主帅，对于奶牛们应该如何列队十分讲究。具体地说，他拒绝为一个子段拍照，除非它形成一个**回文串**，即对于所有不超过子段长度的正整数 $i$，从子段左端开始的第 $i$ 头奶牛的品种必须与从子段右端开始的第 $i$ 头奶牛的品种相同。每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。

对于队伍的 $\frac{N(N+1)}{2}$ 个连续子段的每一个，计算将该子段重新排列成回文串所需的最小换位次数（如果不可能这样做则为 $-1$）。单次换位是在子序列中取两头相邻的奶牛并交换。输出所有这些次数之和。

注意对每个连续子段所需的换位次数是独立计算的（奶牛们会在照片拍摄之间返回她们的起始位置）。

输入队伍，用一个长为 $N$ 的字符 G 和 H 组成的字符串表示。

输出队伍的所有 $\frac{N(N+1)}{2}$ 个连续子段的前述数量之和。