Farmer John 最近购入了 N 头新的奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。

奶牛目前排成一排，Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。

然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。

在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛的照片，都扔掉了。

给定奶牛的排列方式，请帮助 Farmer John 求出他会扔掉多少张孤独的照片。

如果两张照片以不同位置的奶牛开始或结束，则认为它们是不同的。

输入格式
输入的第一行包含 N。

输入的第二行包含一个长为 N 的字符串。如果队伍中的第 i 头奶牛是更赛牛，则字符串的第 i 个字符为 G。否则，第 i 头奶牛是荷斯坦牛，该字符为 H。

输出格式
输出 Farmer John 会扔掉的孤独的照片数量。

数据范围
3≤N≤5×10^5

输入样例：
5
GHGHG
输出样例：
3

思路 ：

• 直接从孤独的照片入手，即连续的大于等于三头牛，且其中只有一个是H，或者其中只有一个是G的情况，这样的串的延伸范围是很有限的
• 第一种情况，只有一个是H。分成三种：1）H是中间的，左右都有若干个G，这种情况是H左边连续的G的个数乘上H右边连续的G的个数；2）H是最左边的，右边有大于等于两个G，这种情况是右边的G的个数-1；3）H是最右边的，左边有大于等于两个G，这种情况是左边的G的个数-1
• 第二种情况，只有一个是G，同上。抽象化来说就是要统计出左右分别与当前这个字母不同的字母的连续的个数：
• 左边：设置两个变量h和g分别表示当前连续的h和连续的g的个数，从左往右遍历
• 右边：设置两个变量h和g分别表示当前连续的h和连续的g的个数，从右往左遍历
• long long

#include 
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;char str[N];
int n, l[N], r[N];int main() {cin >> n >> str;for (int i = 0, h = 0, g = 0; i < n; ++ i) {if (str[i] == 'H') l[i] = g, g = 0, h ++ ;else l[i] = h, h = 0, g ++ ;}for (int i = n - 1, h = 0, g = 0; i >= 0; -- i) {if (str[i] == 'H') r[i] = g, g = 0, h ++ ;else r[i] = h, h = 0, g ++ ;}ll ans = 0;for (int i = 0; i < n; ++ i) {ans += (ll)l[i] * r[i] + max(l[i] - 1, 0) + max(r[i] - 1, 0);}cout << ans;
}