Time limit per test: 0.75
Memory limit: 65536
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 "
" can be transformed to the palindrome "
" using 4 swaps:
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.
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.