[HAOI2009] 求回文串

题目描述

所谓回文串,就是对于给定的字符串,正着读和反着读都一样,比如 ABCBA 就是一个回文串,ABCAB 则不是。我们的目标是对于任意输入的字符串,不断将第 $i$ 个字符和第 $i+1$ 个字符交换,使得该串最终变为回文串。求最少交换次数。

输入输出格式

输入格式


一个由大写字母字母组成的字符串。

输出格式


若能经过有限次操作能将原串变为回文串,则输出最少操作次数;否则输出 $-1$。

输入输出样例

输入样例 #1

SHLLZSHZS

输出样例 #1

4

说明

### 样例说明 1. 交换 $\tt L$ 和 $\tt Z$ 变成 $\tt SHLZLSHZS$; 2. 交换 $\tt L$ 和 $\tt Z$ 变成 $\tt SHZLLSHZS$; 3. 交换 $\tt L$ 和 $\tt S$ 变成 $\tt SHZLSLHZS$; 4. 交换 $\tt H$ 和 $\tt Z$ 变成 $\tt SHZLSLZHS$。 ### 数据范围 - $40\%$ 的数据,长度 $\leq50000$; - $100\%$ 的数据,长度 $\leq10^6$。