D. Мишка и компания
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мишка Лимак подготавливает задачи для соревнования по программированию. Принято, что в задачах не упоминаются названии компании-спонсора соревнования, поэтому Лимак собирается изменить некоторые слова, чтобы удовлетворить этому ограничению. Чтобы условие все еще можно было читать, он хочет изменить каждое слово как можно меньше.

У Лимака есть слово s, состоящее из заглавных букв латинского алфавита. За один шаг он может поменять местами две соседние буквы в слове. Например, он может преобразовать слово «ABBC» в «BABC» или «ABCB» за один шаг.

Лимак хочет за несколько шагов преобразовать слово так, чтобы в нем не встречалась подстрока «VK» (то есть, не было бы буквы «V», сразу за которой идет буква «K»). Можно показать, что это возможно сделать с любым словом s.

Какое минимальное число шагов должен сделать Лимак для этого?

Входные данные

Первая строка содержит целое число n (1 ≤ n ≤ 75) — длина слова.

Во второй строке находится слово s, состоящее из заглавных букв латинского алфавита. Длина слова равна n.

Выходные данные

Выведите одно целое число — минимальное число шагов, которое должен сделать Лимак для того, чтобы получить слово без подстроки «VK».

Примеры
Входные данные
4
VKVK
Выходные данные
3
Входные данные
5
BVVKV
Выходные данные
2
Входные данные
7
VVKEVKK
Выходные данные
3
Входные данные
20
VKVKVVVKVOVKVQKKKVVK
Выходные данные
8
Входные данные
5
LIMAK
Выходные данные
0
Примечание

В первом примере начальное слово — «VKVK». Минимально возможное число шагов равно 3. Оптимальная последовательность шагов показана ниже:

  1. Поменять местами две последние буквы. Слово станет равно «VKKV».
  2. Поменять местами две первые буквы. Слово станет равно «KVKV».
  3. Поменять местами вторую и третью буквы. Слово станет равно «KKVV». Очевидно, в слове теперь нет подстроки «VK».

Во втором примере есть две оптимальные последовательности шагов. Одна из них это «BVVKV»  →  «VBVKV»  →  «VVBKV». Другая — «BVVKV»  →  «BVKVV»  →  «BKVVV».

В пятом примере можно оставить слово как есть.