P7993 [USACO21DEC] Lonely Photo B

Farmer John has recently purchased $N$ new cows ($3 \le N \le 5 \times 10^5$). Each cow is either a Guernsey or a Holstein. The cows are currently standing in a line, and Farmer John wants to take a photo of every contiguous sequence of at least three cows. However, he does not want to take photos in which there is exactly one Guernsey cow, or exactly one Holstein cow—he thinks that such an unusual cow would feel lonely and unnatural. After taking a photo for every contiguous sequence of at least three cows, he throws away all "lonely" photos, meaning photos that contain exactly one Guernsey cow or exactly one Holstein cow. Given the arrangement of the cows, help Farmer John compute how many lonely photos he will throw away. Two photos are considered different if they start or end at different cows.

The first line contains $N$. The second line contains a string of length $N$. If the $i$-th cow in the line is a Guernsey, then the $i$-th character of the string is `G`. Otherwise, the $i$-th cow is a Holstein, and the character is `H`.

Output the number of lonely photos that Farmer John will throw away.

[Sample Explanation] In this example, every substring of length $3$ contains exactly one Guernsey cow or exactly one Holstein cow, so these substrings represent lonely photos and will be thrown away by Farmer John. All longer substrings (`GHGH`, `HGHG`, and `GHGHG`) are acceptable. [Constraints] - Test cases 2-4 satisfy $N \le 50$. - Test cases 5-10 satisfy $N \le 5000$. - Test case 11 has no additional constraints. Note that the answer for this test case may not fit in a standard 32-bit integer type. You may need to use a larger integer type (for example, the 64-bit `"long long int"` type in C++). Translated by ChatGPT 5