Minimum Adjacent Swaps to Palindrome

Given a string s, your task is to determine the minimum number of adjacent swaps required to transform the string into a palindrome. In each operation, you may swap the character at position i with the character at position i+1.

A palindrome is a string that reads the same forwards and backwards. For example, ABCBA is a palindrome, while ABCAB is not.

The minimum number of swaps needed to achieve a palindrome is defined as follows:

\[ \text{result} = \min \left\{ \text{number of adjacent swaps required to convert } s \text{ to a palindrome} \right\} \]

If it is not possible to rearrange s into a palindrome, output -1.

inputFormat

The input consists of a single line that contains the string s (with length at most 10⁵). The string consists of only uppercase or lowercase English letters.

outputFormat

Output a single integer, which is the minimum number of adjacent swaps required to convert the string into a palindrome. If it is impossible, output -1.

sample

abba

0