패티오

카이므란은 빨간색과 파란색 두 가지 색의 타일로 정사각형 바닥을 만들려고 한다. 바닥은 다음 그림처럼 보여야 한다(색은 시간이 지나면서 조금 바랜다).

그림 1: 카이므란이 만든 완벽한 바닥 중 하나

더 구체적으로, 바닥은 정사각형이어야 한다. 한 색의 타일은 정사각형의 테두리로 쓰이며, 테두리는 정확히 한 타일 두께여야 한다. 다른 색의 타일은 나머지 부분을 채우는 데 쓴다. 정사각형의 한 변은 적어도 3개의 타일로 이루어져야 한다.

카이므란에게는 빨간색과 파란색 정사각형 타일이 길게 들어 있는 파일이 있다. 모든 타일의 크기는 같다. 카이므란은 이 파일에서 타일 일부를 골라 바닥에 쓴다. 파일을 다루기는 번거로우므로, 고른 타일들은 파일에서 연속된 부분 수열을 이뤄야 한다.

공사를 시작하기 전에 카이므란은 파일에서 적합한 타일의 연속 부분 수열이 몇 개인지 알아야 한다.

입력은 두 줄이다. 첫째 줄에는 타일 파일의 길이를 나타내는 정수 $N$($1 \le N \le 2 \times 10^5$)이 주어진다. 둘째 줄에는 타일 파일을 나타내는 길이 $N$의 문자열이 주어진다. 문자열에는 두 문자만 등장한다. "X"는 파란 타일을, "O"는 빨간 타일을 나타낸다.

카이므란이 정사각형 바닥을 만들 수 있는 파일 속 연속 부분 수열의 개수를 출력한다.