Nikita 今天收到了一些消息。其中一条消息是代码词 “spbsu”。在该代码词之前和之后，可能还有任意数量的其他消息。其他消息是任意的小写英文字符串。

所有消息都是通过一条秘密通道逐条发送的。因此，通道中的字符串最初是所有消息的拼接。

然而，由于是秘密通道，通道可能会引入噪声：不同的消息可能会相互干扰。形式上，噪声表现为交换操作。在每次交换中，通道选择并交换字符串中两个最初属于不同消息的相邻字符。对于任何特定消息的字符，其相对顺序保持不变。

经过所有交换后，Nikita 收到了最终的字符串。给定最终的字符串，求通道所做的最少交换次数。

输入格式

第一行包含一个整数 $n$：接收到的字符数 ($5 \le n \le 10^5$)。

下一行包含一个由 $n$ 个小写英文字符组成的字符串 $s$：Nikita 接收到的最终字符串。保证该字符串是上述过程的结果。

输出格式

输出一个整数：问题的答案。

样例

样例输入 1

6
spbssu

样例输出 1

1

样例输入 2

15
spongebaseurban

样例输出 2

11