Palindrome

Interview

Time limit1sMemory limit1024 MB

Summary

Given a string of a and b, find the fewest adjacent swaps that turn it into a palindrome, or -1 if that is impossible.

Level: Medium4 of 10
Topics: String, Greedy, Two pointers
Solved: No attempts yet

Problem

Bajtek learned what a palindrome is at an informatics club. A palindrome is a word that reads the same from left to right as from right to left. For example, oko, kajak, kobyłamamałybok, and ababbaba are palindromes, while kajaki, zoo, alamakota, and abaababa are not.

Excited by his new knowledge, Bajtek quickly opened a notepad and wrote a word made of the letters a and b. After a moment he realized the word does not have to be a palindrome. He decided to fix it. In one second, he can choose two adjacent letters and swap them. Using a sequence of such moves (or none at all), can he turn his word into a palindrome? If so, what is the minimum number of seconds these changes take? Write a program that computes this.

Input

The only line contains a non-empty word written in Bajtek's notepad. The word contains only the characters a and b, and its length does not exceed 200,000.

Output

Print one integer, the minimum number of seconds needed to turn Bajtek's word into a palindrome. If it is impossible, print -1.

Hint

In the first sample, Bajtek can, for example, perform the sequence abbaaab → babaaab → baabaab, which turns the word into a palindrome in two seconds. It can be shown that no faster way exists.

In the second sample, the word can be ab or ba. Neither is a palindrome, so Bajtek cannot complete the task.

Examples2

Example 1
Input
```
abbaaab
```
Expected output
```
2
```
Example 2
Input
```
ab
```
Expected output
```
-1
```