반대칭성

0과 1로 이루어진 문자열을 생각하자. 문자열 $x$에 대하여, $x^R$은 $x$를 뒤집은(즉, 거꾸로 읽은) 문자열을 뜻하고, $\bar{x}$는 $x$의 모든 0을 1로, 모든 1을 0으로 바꾼 문자열을 뜻한다.

비어 있지 않은 문자열 $x$가 다음 조건을 만족하면 반대칭(antisymmetric) 이라고 한다: $x$의 모든 위치 $i$에 대하여, 뒤에서 $i$번째 문자가 앞에서 $i$번째 문자와 서로 다르다. 0과 1로 이루어진 문자열의 경우, 이는 $x = \bar{x}^R$인 것과 정확히 같은 뜻이다. 예를 들어 00001111과 010101은 반대칭이지만, 1001은 반대칭이 아니다.

주어진 0과 1로 이루어진 문자열에서, 반대칭인 연속 부분 문자열(비어 있지 않은 것)의 개수를 구하여라. 내용이 같더라도 서로 다른 위치에서 나타났다면 각각 따로 센다.

첫째 줄에 문자열의 길이를 나타내는 정수 $n$ $(1 \le n \le 500\,000)$이 주어진다. 둘째 줄에 길이가 $n$이고 0과 1로만 이루어진 문자열이 공백 없이 주어진다.

주어진 문자열의 연속 부분 문자열(비어 있지 않은 것) 중 반대칭인 것의 개수를 한 줄에 하나의 정수로 출력한다.

문자열 11001011에서 반대칭인 부분 문자열은 01(두 번 등장), 10(두 번 등장), 0101, 1100, 001011이며, 모두 합하면 7개이다.