配点 : 100 点
問題文
N 将举行石头剪刀布锦标赛,人们将参加。参与者是人 它被称为 1、人 2、\ldots、人 N 。每个参与者都有自己最喜欢的动作,并且每场比赛只使用自己最喜欢的动作。
参与者最喜欢的动作是
由R, P, S 组成
它是一个 N 的字符串 S 代表。人 i 最喜欢的举动是S 的 i 文字目 S_i 。这里的字符 R 很好,P 是标准值,S 代表剪刀。
在比赛中,人们 将 1、人 2、\ldots、人 N 按此顺序水平排列后, 参加超过0 “比赛”。 “比赛”的进行如下。
- 列中相邻 2 就像玩石头剪子布,却没有成为爱子一样。 2 随机选择一个人,让他们玩石头、剪子、布。让失败者滚出队伍。
一旦“比赛”无法再进行,队列中剩下的每个人都会获胜。尤其是那些还在排队的人。 1 如果只剩下一个人,则该人将是唯一的获胜者。
求单独能获胜的人数。
石头、剪刀、布规则
石头剪刀布的结果是2 根据该人的手牌确定如下。- 当一个人是粘子,另一个人是剪刀时,滚粘子的人获胜,滚砍子的人输。
- 当一个人出拳而另一个人打出标准杆时,打出拳击的人获胜,打出标准杆的人输。
- 如果一名球员打出标准杆,另一名球员打出总杆,那么打出标准杆的人获胜,打出总杆的人输。
- 当双方玩家做出相同的动作时,Aiko(平局)
制約
- N 是一个整数
- 2 \leq N \leq 3 \times 10^5
- S 是
R,P,S组成 它是一个 N 的字符串
部分点
这个问题有多个部分点。
- 2 \leq N \leq 50 的数据集 如果正确答案是满足 10 点。
- 2 \leq N \leq 3000 的数据集 如果正确答案是满足 50 点。
入力
输入是按以下格式从标准输入给出的。
N S
出力
答案 请在 1 行输出。
入力例 1
4 RSPR
出力例 1
2RSPR
例如,如果使用以下程序举行锦标赛, 3 是唯一的获胜者。
- 人 1 和人 2 人们玩石头剪刀布 1 获胜。
- 人 1 和人 3 人们玩石头剪刀布 3 获胜。
- 人 3 和人 4 人们玩石头剪刀布 3 获胜。
此外,人们 1 可能是唯一的赢家。另一方面,人们 2 和人 4 独自一人没有获胜的机会。
入力例 2
3 RSR
出力例 2
0RSR
必须 2 将会留下不止一个人。
入力例 3
6 SRPPSR
出力例 3
3SRPPSR 有