Description

Xiao L is currently playing a low-level version of 2-pop game, which is one-dimensional and can only eliminate two adjacent elements at a time.

Now, he has a string of length $n$ consisting only of lowercase letters. We call a string erasable if and only if it can be manipulated several times to make it an empty string.

Each operation can delete two adjacent identical characters from the string, and the remaining string will be concatenated together after the operation.

Xiao L wants to know how many non empty continuous substrings of this string are removable.

Input

The first line of input contains a positive integer $n$, representing the length of the string.

The second line of input contains a string of length $n$ consisting only of lowercase letters, representing the string asked in the question.

Output

Output a line containing an integer representing the answer to the question asked.

Samples

8
accabccb

5

Tips

[Sample Input 1 Explanation]

There are a total of $5$ continuous substrings that can be eliminated, namely cc、acca、cc、bccb、accabccb.

[Example 2]

See game/game2.in and game/game2.ans in the player directory.

[Example 3]

See game/game3.in and game/game3.ans in the player directory.

[Example 4]

See game/game4.in and game/game4.ans in the player directory.

[Data Range]

For all test data, there is $1 \le n \le 2 \times 10^6$, and the query string is only composed of lowercase letters.

Special property A: Each character in a string is independently and equally selected from the character set.

Special property B: A string is composed only of a and b.