P9753 [CSP-S 2023] Elimination Game

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.

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 one line containing an integer, which is the answer to the query.

**[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. | Test Point | $n\leq$ | 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`. Translated by ChatGPT 5