题目背景

原题为 P7993 [USACO21DEC] Lonely Photo B

题目描述

ybooG 是验实桥杜中学的信息学奥赛教练。他想给他的学生们拍照片。

已知他有 $N$ 个学生 $(3 \le N \le 5 \times 10^5)$，每个同学要不就是13班的（记作G），要不就是14班的（记作H）。

现在这 $N$ 个同学排成一排，ybooG 想要为每个连续不少于三个同学的序列拍摄一张照片。不过这么多的照片中，有一些照片是 孤独的：这些照片满足只有一个同学是13班或者只有一个同学是14班的。

在为每个连续不少于三个同学的序列拍摄了一张照片后，ybooG 把所有 "孤独的"照片 都扔掉了。

现在给定同学的排队方式，请帮助 ybooG 求出他会扔掉多少张孤独的照片。如果两张照片以不同的同学开始或结束，则认为它们是不同的。

输入格式

输入的第一行包含 $N$。

输入的第二行包含一个长为 $N$ 的字符串。如果队伍中的第 $i$ 个同学是13班的，则字符串的第 $i$ 个字符为 G。否则，第 $i$ 个同学是14班的，该字符为 H。

输出格式

输出 ybooG 会扔掉的孤独的照片数量。

输入输出样例 #1

输入 #1

5
GHGHG

输出 #1

3

说明/提示

【样例解释】

这个例子中的每一个长为 3 的子串均恰好包含一个13班的或者14班的同学——所以这些子串表示孤独的照片，并会被 ybooG 扔掉。所有更长的子串（GHGH、HGHG 和 GHGHG）都可以被接受。

【数据范围】

• 测试点 1-3 满足 $N \le 50$。
• 测试点 4-9 满足 $N \le 5000$。
• 测试点 10 没有额外限制。