Вам задана строка \(s\). Вам необходимо перевернуть эту строку. То есть последняя буква строки должна стать первой, предпоследняя буква строки должна стать второй, и так далее. Например, перевернутая строка «abddea» равна «aeddba». Для достижения цели (то есть для переворота заданной строки) вы можете менять местами соседние элементы строки.
Перед вами стоит задача определить минимальное количество обменов соседних элементов строки, необходимых для того, чтобы перевернуть строку.
Выходные данные
Выведите минимальное количество обменов соседних элементов строки, необходимых для того, чтобы перевернуть строку.
Примечание
В первом примере нужно сначала поменять местами третью и четвертую буквы, тогда строка станет равна «aazaa». Затем нужно поменять вторую и третью буквы, тогда строка станет равна «azaaa». Таким образом, за два обмена соседних букв мы сможем перевернуть заданную строку.
Во втором примере заданная строка является палиндромом, то есть перевернутая строка равна исходной строке, поэтому никаких обменов делать не нужно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
aaaza
|
2
|
|
2
|
6
cbaabc
|
0
|
|
3
|
9
icpcsguru
|
30
|