코나미 코드

많은 옛날 게임에서 흔히 쓰이는 치트 코드는 이른바 코나미 코드로, upp upp ned ned vänster höger vänster höger B A 순서로 이루어진다.

당신은 게임을 프로그래밍하고 있으며, 코나미 코드를 입력하면 활성화되는 치트 기능을 넣으려고 한다. 하지만 여기에 변형을 주어, 코나미 코드의 버튼들 사이에 다른 버튼을 최대 $K$번 누르는 것을 허용하려고 한다.

$K = 3$이면 추가 버튼 입력을 세 번 삽입할 수 있다는 뜻이다. 따라서 upp upp ned **vänster** ned vänster **B B** höger vänster höger B A은 올바른 코나미 코드이며, 추가된 세 번의 버튼 입력은 굵게 표시되어 있다.

이제 버튼 입력의 순서가 주어졌을 때, 그 안에 코나미 코드가 나타나기 위해 필요한 가장 작은 $K$ 값을 구하는 프로그램을 작성해야 한다. 코나미 코드의 첫 번째 버튼 입력보다 앞서 일어난 버튼 입력과 마지막 버튼 입력보다 뒤에 일어난 버튼 입력은 세지 않는다는 점에 유의하라. 즉, **B B vänster** upp upp ned **vänster** ned vänster **B B** höger vänster höger B A **A B upp** 순서에 대해서도 답은 여전히 $K = 3$이다.

점수

• [7 poäng] $N \le 11$.

• [11 poäng] $N \le 100$.

• [12 poäng] $N \le 3000$.

• [20 poäng] $N \le 200\,000$.

입력은 버튼 입력의 순서를 나타내는 $N$개의 문자로 이루어진 한 줄을 포함한다. 이 순서는 문자 U, N, V, H, B, A로 주어지며, 이 문자들은 버튼 입력 upp, ned, vänster, höger, B, A을 나타낸다.

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

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