给你一个字符串 $$$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”。因此,可以在两次交换中反转字符串。
由于第二个示例中的字符串是回文,因此您不必执行任何操作来反转它。