AT_abc365_d [ABC365D] AtCoder Janken 3

题目描述

高桥和青木玩了 $N$ 次石头剪刀布。注：在这个游戏中，石头赢剪刀，剪刀赢纸，纸赢石头。

青木的动作由长度为 $N$ 的字符串 $S$ 表示，字符串由 R、P 和 S 组成。$S$ 中的第 $i$ 个字符表示青木在第 $i$ 盘棋局中的棋步：R 表示石头，P 表示 纸，S 表示剪刀。

高桥的棋步满足以下条件：

• 高桥从未输给过青木。
• 对于 $i=1,2,…,N−1$，高桥在第 $i$ 对局中的棋步与他在第 $i+1$ 对局中的棋步不同。

求高桥可能赢的最大对局数。

可以保证存在一个满足上述条件的高桥下棋顺序。

输入格式

输入共有 $2$ 行

第一行 $1$ 个整数 $N$

第二行为 $1$ 个只包含 R、P 和 S 的长度为 $N$ 字符串 $S$

输出格式

输出只有 $1$ 行，为高桥可能赢的最大对局数

输入输出样例 #1

输入 #1

6
PRSSRS

输出 #1

5

输入输出样例 #2

输入 #2

10
SSSSSSSSSS

输出 #2

5

输入输出样例 #3

输入 #3

24
SPRPSRRRRRPPRPRPSSRSPRSS

输出 #3

18

说明/提示

$1 \le n \le 2\times 10^5$