무도실
면접 대비시간 제한2초메모리 제한512 MB
길이가 최대 10^6인 'a'와 'b' 문자열이 주어질 때, a와 b의 개수가 같은 부분 문자열의 수를 센다.
문제
파데그라스 교수의 무도실에 남학생과 여학생 n명이 등록했다. 교수는 이들을 한 줄로 세우고, 첫 수업을 위해 연속으로 서 있는 학생들 중에서 남학생과 여학생의 수가 같은 그룹을 뽑으려 한다. 교수가 고를 수 있는 경우의 수는 몇 가지인가?
입력
첫째 줄에 n이 주어진다 (1 ≤ n ≤ 10^6). 둘째 줄에 세운 줄을 나타내는 n개의 문자로 이루어진 문자열이 주어진다. 각 문자는 a 또는 b이며, a는 여학생, b는 남학생을 나타낸다.
출력
첫째 줄에 조건을 만족하는 그룹을 고를 수 있는 경우의 수를 출력한다.