325. Palindrome

Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



You are given a word. You can perform the only operation to this word: swap two adjacent letters. Your task is to make a palindrome from the original word using the minimal number of swaps. The palindrome is a word which is spelled the same way when reading from left to right and from right to left.

For example, the word "
ABBYY
" can be transformed to the palindrome "
YBABY
" using 4 swaps:

ABBYY
BABYY
BAYBY
BYABY
YBABY


Input
The only line of the input contains the given word. The word is written using capital Latin letters. The length of the word is no less than one and no more than 1000000 letters.

Output
Write the minimum possible number of swaps required to get a palindrome from the given word to the output. If it is impossible to get a palindrome, write -1 to the output.

Example(s)
sample input
 
sample output
 
MISSISSIPPI

13