시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 238 76 65 54.167%

문제

국내 생물학자들은 기존에 보지 못했던 신기한 DNA 분자를 발견했다. 이 분자는 A와 B로만 이루어진 N글자로 나타낼 수 있다. 이 분자는 계속해서 돌연변이를 한 다음에, A로만 된 분자로 변한다.

어느날, 이 분자를 연구하던 학자들은 두 종류의 돌연변이를 일으킨다는 사실을 알아내었다. 첫 번째 돌연변이는 분자의 한 글자가 다른 글자로 바뀌는 것이다. (A -> B 또는 B -> A) 두 번째 돌연변이는 첫 K개 글자를 모두 다른 글자로 바꾸는 것이다

DNA 분자가 주어졌을 때, 돌연변이를 최소 몇 번 일으키면, 전부 A로 된 분자가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 분자의 길이 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄에는 분자를 이루는 N글자가 주어진다.

출력

첫째 줄에 최소 몇 번 돌연변이를 일으키면 A로만 된 분자가 되는지 출력한다.

예제 입력

5
BBABB

예제 출력

2

힌트