Little L is playing a simplified version of a matching game. This version of the game is one-dimensional, and only two adjacent elements can be removed at a time.
He has a string of length $n$ consisting only of lowercase letters. We call a string "erasable" if and only if it can be transformed into an empty string through a sequence of operations.
In each operation, he can remove two adjacent identical characters from the string, after which the remaining parts of the string are concatenated.
Little L wants to know how many non-empty contiguous substrings of this string are erasable.
Input
The first line contains a positive integer $n$, representing the length of the string.
The second line contains a string of length $n$ consisting only of lowercase letters, representing the string in question.
Output
Output a single integer representing the answer to the problem.
Examples
Input 1
8 accabccb
Output 1
5
Note 1
There are 5 erasable contiguous substrings: cc, acca, cc, bccb, and accabccb.
Input 2
(See game/game2.in in the contestant directory)
Output 2
(See game/game2.ans in the contestant directory)
Input 3
(See game/game3.in in the contestant directory)
Output 3
(See game/game3.ans in the contestant directory)
Input 4
(See game/game4.in in the contestant directory)
Output 4
(See game/game4.ans in the contestant directory)
Constraints
For all test cases: $1 \le n \le 2 \times 10^6$, and the string consists only of lowercase letters.
| Test Cases | $n \le$ | Special Property |
|---|---|---|
| $1 \sim 5$ | $10$ | None |
| $6 \sim 7$ | $800$ | None |
| $8 \sim 10$ | $8000$ | None |
| $11 \sim 12$ | $2 \times 10^5$ | A |
| $13 \sim 14$ | $2 \times 10^5$ | B |
| $15 \sim 17$ | $2 \times 10^5$ | None |
| $18 \sim 20$ | $2 \times 10^6$ | None |
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'.