DNA Sequencing — Palindrome Transformation Cost

For each contiguous substring of the string, compute the minimum number of characters to change so that the substring becomes a palindrome, then find the sum of these costs over all substrings. This site follows the original problem's in-order palindrome definition, so characters cannot be rearranged.

See below for this site's input format and constraints.

输入格式

A single line containing a string dna of lowercase English letters only. This site uses 1≤|dna|≤100000.

输出格式

Output the sum of the palindrome change costs over all contiguous substrings.

样例 1

输入：

asbsd

输出：

11

样例 2

输入：

a

输出：

0

样例 3

输入：

aaa

输出：

0