함께 빌릴 자전거

문제

공유 자전거 보관소에는 N개의 거치대가 왼쪽부터 오른쪽으로 한 줄로 놓여 있다. 각 거치대에는 자전거가 한 대씩 있으며, 안내판에는 각 자전거의 현재 상태가 문자 하나로 표시되어 있다. 문자열 S의 i번째 문자는 왼쪽에서 i번째 거치대에 있는 자전거의 상태를 뜻한다. 문자 A는 지금 빌릴 수 있는 자전거, 문자 U는 다른 이용자가 사용 예약을 해 둔 자전거, 문자 X는 점검 때문에 빌릴 수 없는 자전거를 뜻한다. 상태 문자는 이 세 가지뿐이다. U와 X는 빌릴 수 없는 이유가 다르지만, 이번에 두 사람이 빌릴 자전거를 고를 때는 모두 선택할 수 없는 상태로 취급한다. 함께 도착한 두 사람은 서로 바로 이웃한 거치대에서 자전거를 한 대씩 빌리려 한다. 따라서 왼쪽에서 i번째와 i+1번째 거치대의 자전거가 모두 A 상태일 때만 그 두 거치대를 하나의 후보 쌍으로 정한다. 두 거치대 사이에 다른 거치대가 있으면 두 자전거가 모두 A여도 후보 쌍이 아니다. 관리자는 실제 대여를 진행하기 전에 가능한 후보 쌍의 개수만 세려 한다. 후보를 하나 셌다고 해서 자전거의 상태가 바뀌지는 않는다. 따라서 한 자전거가 서로 다른 두 후보 쌍에 포함되어도 된다. 예를 들어 A 상태의 자전거 세 대가 연속해 있으면 왼쪽 두 대와 오른쪽 두 대가 각각 후보가 되어 두 쌍으로 센다. 같은 두 거치대에서 누가 어느 자전거를 탈지는 구분하지 않는다. 첫 번째 거치대와 마지막 거치대는 서로 이웃하지 않는다. 거치대가 하나뿐이거나 조건을 만족하는 두 거치대가 없으면 후보 쌍의 개수는 0이다. 주어진 상태 문자열을 보고 두 사람이 선택할 수 있는 후보 쌍의 개수를 구한다.

입력

첫째 줄에 거치대의 개수인 정수 N이 주어진다. 1 ≤ N ≤ 1,000이다.
둘째 줄에 길이가 N인 문자열 S가 주어진다. S는 영문 대문자 A, U, X로만 이루어져 있다.

출력

첫째 줄에 가능한 후보 쌍의 개수를 정수 하나로 출력한다.

8
AAAUAAAX

4

1
A

0

6
AUXAUA

0

출처: Devin.KR 자체 제작