5615 - 提高:完美值

通过次数

3

提交次数

3

时间限制 : 1 秒
内存限制 : 256 MB

定义一个字符串的“完美值”是:修改最少字符数量使得其变成回文串的修改次数。例如,"abca"的完美值是1。任何回文串的完美值是0。

输入

一个仅包含小写字母的字符串。长度不超过200000

输出

所有连续子串的回文值之和。

样例

输入

abca

输出

6

提示

所有长度不小于2的子串的完美值都是1。其余子串完美值是0。