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