Bear Limak 为编程竞赛准备问题。当然,在声明中提及赞助商名称是不专业的。利马克认真对待此事,他将更改一些措辞。为了使其仍然可以阅读,他会尽量少地修改每个单词。
Limak 有一个由大写英文字母组成的字符串 s。他一步就能交换字符串中两个相邻的字母。例如,他可以一步将字符串“ABBC”转换为“BABC”或“ABCB”。
Limak 想要获取一个不包含子字符串“VK”的字符串(即不应有紧随字母“K”的字母“V”)。可以很容易地证明,对于任何初始字符串 s 都是可能的。
Limak 最少可以移动多少步?
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 75) - 字符串的长度。
第二行包含字符串s,由大写英文字母组成。字符串的长度等于n。
输出
打印一个整数,表示 Limak 可以执行的最小可能移动次数,以获得不带子字符串“VK”的字符串。
示例
输入 #1
4 VKVK
输出 #1
3
输入 #2
5 BVVKV
输出 #2
2
输入 #3
7 VVKEVKK
输出 #3
3
输入#4
20 VKVKVVVKVOVKVQKKKVVK
输出#4
8
输入 #5
5 LIMAK
输出 #5
0
注意
在第一个示例中,初始字符串是“VKVK”。最小可能的移动次数为 3。一种最佳的移动顺序是:
1. 交换最后两个字母。该字符串变为“VKKV”。
2. 交换前两个字母。该字符串变为“KVKV”。
3. 交换第二个和第三个字母。该字符串变为“KKVV”。事实上,这个字符串没有子字符串“VK”。
在第二个示例中,有两个最佳的移动序列。一是“BVVKV”→“VBVKV”→“VVBKV”。另一种是“BVVKV”→“BVKVV”→“BKVVV”。
在第五个示例中,不需要交换。