코나미 코드

옛날 게임에서 흔히 쓰이는 치트 코드 중 하나로 코나미 코드가 있다. 이는 위 위 아래 아래 왼쪽 오른쪽 왼쪽 오른쪽 B A 순서로 이루어져 있다.

당신은 게임을 만들면서 코나미 코드를 입력하면 발동되는 치트를 넣으려 한다. 다만 재미를 위해, 코나미 코드 사이에 최대 $K$개의 다른 버튼을 눌러도 되도록 하려 한다.

$K = 3$이면 추가로 세 번의 버튼 입력을 끼워 넣을 수 있다는 뜻이다. 따라서 위 위 아래 왼쪽 아래 왼쪽 B B 오른쪽 왼쪽 오른쪽 B A는 올바른 코나미 코드이며, 세 번의 추가 입력은 굵게 표시되어 있다.

이제 버튼 입력 순서가 주어질 때, 그 안에 코나미 코드가 나타나기 위해 필요한 최소 $K$ 값을 구하는 프로그램을 작성하라. 첫 번째 코나미 코드 입력 전과 마지막 코나미 코드 입력 후에 일어나는 버튼 입력은 세지 않는다. 따라서 B B 왼쪽 위 위 아래 왼쪽 아래 왼쪽 B B 오른쪽 왼쪽 오른쪽 B A A B 위에 대해서도 여전히 $K = 3$이라고 답해야 한다.

입력은 $N$개의 문자로 이루어진 한 줄이다. 버튼 입력 순서가 주어지며, 위, 아래, 왼쪽, 오른쪽, B, A를 뜻하는 U, N, V, H, B, A 문자들로 구성된다.

코나미 코드가 버튼 입력의 부분 수열로 존재함이 보장된다.

문제에서 설명한 정수 $K$를 한 줄에 출력한다.