Minimum Adjacent Swaps to Form Palindrome

You are given a string s consisting of lowercase English letters. Your task is to determine the minimum number of adjacent swaps required to transform s into a palindrome. If it is impossible to form a palindrome from s, output -1.

A string can be rearranged into a palindrome if and only if at most one character appears an odd number of times. Once verified, one can simulate the process by matching letters from the outer ends towards the center, swapping adjacent characters to reposition the matching characters appropriately.

For example, the string mamad requires 3 swaps to become a palindrome, whereas asflkj cannot be rearranged into a palindrome, so the answer is -1.

The formula for a necessary condition is: \( \text{oddCount} \le 1 \), where \( \text{oddCount} \) is the number of characters with odd frequency.

inputFormat

The input is read from standard input (stdin) and consists of a single line containing the string s (1 ≤ |s| ≤ 10⁵), composed only of lowercase English letters.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of adjacent swaps required to transform the string into a palindrome, or -1 if it is not possible.

## sample

mamad

3

</p>