Migrated from Lutece 3174 魔法练习

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小明找到魔法师，想要学习一种能够改变字符串结构的魔法。但是小明的能力显然不足以直接影响整个字符串的结构，所以魔法师决定从最简单的魔法教起。 经过一天的练习，小明终于学会了最简单的魔法：交换字符串相邻两个位置的字符。为了检验学习成果，魔法师给小明留下了一项练习：将一整个字符串翻转。但是一天的学习已经耗尽了小明的精力，所以小明想要尽快完成这项练习。

魔法师留下的字符串长度为 $n$ ，全部由小写字母构成，小明每次使用魔法可以交换字符串中相邻的两个字符，小明想要知道最少需要使用多少次魔法才能将字符串翻转过来。

Input

第一行包含一个正整数 $n$ ，表示给定字符串的长度。

第二行包含一个字符串 $S$ ，仅包含小写英文字母。

Output

输出一个正整数，表示最小明最少需要使用多少次魔法才能完成这项练习。

Samples

5
aaaba

2

9
uestcxcpc

29

Constraints

$1 \leq n \leq 200000$

Note

对于第一个样例： 第一次交换第 $3$ 位与第 $4$ 位，得到字符串 $aabaa$ ， 第二次交换第 $2$ 位与第 $3$ 位，得到字符串 $abaaa$ ， 故答案为 $2$ 。