#USACOC2214A. Lonely Photo

Lonely Photo

Farmer John 最近购入了 NN 头新的奶牛,每头奶牛的品种是更赛牛(Guernsey)或荷斯坦牛(Holstein)之一。

奶牛目前排成一排,Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。 然而,他不想拍摄这样的照片,其中只有一头牛的品种是更赛牛,或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。 在为每个连续不少于三头奶牛的序列拍摄了一张照片后,他把所有「孤独的」照片,即其中只有一头更赛牛或荷斯坦奶牛的照片,都扔掉了。

给定奶牛的排列方式,请帮助 Farmer John 求出他会扔掉多少张孤独的照片。如果两张照片以不同的奶牛开始或结束,则认为它们是不同的。

  • 3N5×1053 \le N \le 5 \times 10^5

输入格式

输入的第一行包含 NN

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

输出格式

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

5
GHGHG
5
GHGHG

测试点性质

  • 测试点 2-4 满足 N50N \le 50
  • 测试点 5-10 满足 N5000N \le 5000
  • 为了增加一些挑战,测试点 11 没有额外限制。注意这个测试点的答案可能无法用标准的 32 位整数型存储,你可能需要使用更大的整数类型(例如,C++ 中 64 位的 long long int 类型)。

题目提供者

供题:Nick Wu