Вам дана строка \(s\), состоящая из строчных букв латинского алфавита. За одну операцию вы можете поменять местами любые два символа в строке \(s\).
Строка \(s\) длины \(n\) называется антипалиндромом, если \(s[i] \ne s[n - i + 1]\) для каждого \(i\) (\(1 \le i \le n\)). Например, строки «codeforces», «string» являются антипалиндромами, а строки «abacaba», «abc», «test» — не являются.
Определите минимальное число операций, необходимое, чтобы сделать из строки \(s\) антипалиндром, или выведите \(-1\), если это невозможно.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимое, чтобы сделать из строки \(s\) антипалиндром, или \(-1\), если это невозможно.
Примечание
В первом примере строка «codeforces» изначально является антипалиндромом, поэтому ответом является \(0\).
Во втором примере можно показать, что строку «abc» нельзя сделать антипалиндромом с помощью таких операций, поэтому ответом является \(-1\).
В третьем примере в строке «taarrrataa» достаточно переставить местами второй и пятый символы, и новая строка «trararataa» будет антипалиндромом, поэтому ответом является \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
10
codeforces
3
abc
10
taarrrataa
10
dcbdbdcccc
4
wwww
12
cabbaccabaac
10
aadaaaaddc
14
aacdaaaacadcdc
6
abccba
12
dcbcaebacccd
|
0
-1
1
1
-1
3
-1
2
2
2
|