Antisymmetry

Byteasar studies certain strings of zeroes and ones. Let S be such a string. By Sr we will denote the reversed (i.e., “read backwards”) string S, and by SI we will denote the string obtained from S by changing all the zeroes to ones and ones to zeroes.

Byteasar is interested in antisymmetry, while all things symmetric bore him. Antisymmetry however is not a mere lack of symmetry. We will say that a (nonempty) string S is antisymmetric if, for every position i in S, the i-th last character is different than the i-th (first) character. In particular, a string S consisting of zeroes and ones is antisymmetric if and only if S=SIr. For example, the strings 00001111 and 010101 are antisymmetric, while 1001 is not.

In a given string consisting of zeroes and ones we would like to determine the number of contiguous nonempty antisymmetric fragments. Different fragments corresponding to the same substrings should be counted multiple times.

Input

The first line of the standard input contains an integer N (1 <= N <= 500000) that denotes the length of the string. The second line gives a string of 0 and/or 1 of length N. There are no spaces in the string.

Output

The first and only line of the standard output should contain a single integer, namely the number of contiguous (non empty) fragments of the given string that are antisymmetric.

Example

For the input data:

8 11001011 the correct result is:

7 Antisymmetric fragments are: 01 (occurs twice), 10 (also twice), 0101, 1100, and 001011.

題目鏈接

題意：一個只含有0、1的字符串，這個字符串在將0變成1，將1變成0后進行反轉，如果和原來的字符串完全相同，則稱之為反對稱字符串，現在給你一個0、1的字符串，讓你求有多少個子字符串為反對稱字符串。

解題思路：因為經過0變1,1變0和反轉兩個操作，所以如果這個字符串的長度為奇數，它是不可能成為反對稱字符串的（因為最中間那個肯定不相同），對于一個長度為偶數且為l的字符串，我們只要讓它的第i個字符與第l-i+1（也就是倒數第i個字符）不相同即可，因此我們可以用manacher來解決這個問題。