题目描述

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

输入格式

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

输出格式

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

SHLLZSHZS

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$。