Problem Description

Xiao L is playing a low-spec version of an elimination game. In this version, the game is one-dimensional, and each move can only eliminate two adjacent elements.

Now, he has a string of length $n$ consisting only of lowercase letters. We say a string is eliminable if and only if we can perform some operations on this string to turn it into an empty string.

In each operation, you may delete two adjacent identical characters from the string. After the deletion, the remaining parts of the string will be concatenated together.

Xiao L wants to know: among all non-empty contiguous substrings of this string, how many are eliminable.

Input Format

The first line contains a positive integer $n$, which denotes the length of the string.

The second line contains a string of length $n$ consisting only of lowercase letters, which is the string asked about in this problem.

Output Format

Output one line containing an integer, which is the answer to the query.

8
accabccb

5

Hint

[Sample 1 Explanation]

There are $5$ eliminable contiguous substrings in total: cc, acca, cc, bccb, accabccb.

[Sample 2]

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

[Sample 3]

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

[Sample 4]

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

[Constraints]

For all testdata: $1 \le n \le 2 \times 10^6$, and the queried string consists only of lowercase letters.

Special Property A: Each character in the string is chosen independently and uniformly at random from the character set.

Special Property B: The string consists only of a and b.

Translated by ChatGPT 5