Mazeppa와 친구들은 머리가 아파서 조기 입실을 하려 한다. Mazeppa와 친구들을 포함해 총 명의 학생이 조기 입실을 하기 위해 줄을 서 있다. 줄은 과 로만 이루어진 길이 의 문자열 로 나타나며, Mazeppa 혹은 그의 친구들은 , 그 외의 학생들은 으로 표시된다.
Mazeppa와 친구들은 모두 함께 가장 먼저 조기 입실을 하고 싶어 한다. 최대한 빨리 조기 입실을 하기 위해 Mazeppa와 친구들은 새치기를 하려고 한다. 하지만 새치기는 티가 나면 안 되기 때문에 아래와 같은 방법으로만 새치기를 할 수 있다.
새치기: Mazeppa와 친구들 중 두 명이 연속해서 서 있고, 바로 앞사람이 그들의 친구가 아닌 학생일 때, 두 명이 동시에 앞사람을 제치고 앞으로 이동한다. 즉, 연속한 부분 문자열 을 으로 바꿀 수 있다.
새치기 연산을 원하는 만큼 사용할 수 있을 때, Mazeppa와 친구들을 모두 줄의 맨 왼쪽 끝으로 모으기 위한 최소 연산 횟수를 구해보자.
첫 번째 줄에 학생들의 수 이 주어진다.
두 번째 줄에 줄의 상태를 나타내는 길이 의 문자열 가 주어진다. 문자열 는 과 로만 이루어져 있으며, 이 적어도 하나 존재함이 보장된다.
첫 번째 줄에 Mazeppa와 친구들을 모두 줄의 맨 왼쪽 끝으로 모으기 위한 최소 연산 횟수를 출력한다. 만약 불가능하다면 을 출력한다.
