← 返回题目列表

Codeforces · 1430/E

E. 字符串反转

中文机器翻译题面 查看原题

给你一个字符串 $$$s$$$。你必须反转它——也就是说,第一个字母应该等于反转之前的最后一个字母,第二个字母应该等于反转之前的倒数第二个字母——依此类推。例如,如果您的目标是反转字符串“abddea”,则应该得到字符串“aeddba”。为了实现您的目标,您可以交换字符串的相邻元素。

您的任务是计算反转给定字符串所需执行的最小交换次数。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 200\,000$$$) — $$$s$$$ 的长度。

第二行包含 $$$s$$$ — 由 $$$n$$$ 小写拉丁字母组成的字符串。

输出

打印一个整数 — 为反转字符串而必须执行的相邻元素交换的最少次数。

示例

输入 #1

5
aaaza

输出 #1

2

输入 #2

6
cbaabc

输出 #2

0

输入 #3

9
icpcsguru

输出 #3

30

注意

在第一个示例中,您必须交换第三个和第四个元素,因此字符串变为“aazaa”。然后你必须交换第二个和第三个元素,所以字符串变成“azaaa”。因此,可以在两次交换中反转字符串。

由于第二个示例中的字符串是回文,因此您不必执行任何操作来反转它。