← 返回题目列表

AtCoder · abc365_d

G. AtCoder 猜拳 3

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

高桥和青木玩石头剪刀布 N 次。 [注:本游戏中,石头胜剪刀,剪刀胜布,布胜石头。]

青木的动作用字符串表示 S 长度 N 由字符组成 R, P,和 S。 的 i- 第一个字符 S 表示青木在 i第一场比赛: R 对于摇滚, P 对于纸张,以及 S 剪刀。

高桥的动作满足以下条件:

  • 高桥从未输给青木。
  • 对于 i=1,2,\ldots,N-1,高桥的举动 i- 第局棋与他在 (i+1)第一场比赛。

确定高桥可以赢得的最大比赛数。

保证高桥存在满足这些条件的一系列动作。

约束

  • 1\leq N\leq2\times10 ^ 5
  • S 是一个长度为的字符串 N 组成 R, P,和 S.
  • N 是一个整数。

输入

输入由标准输入按以下格式给出:

N
S

输出

打印高桥可能赢得的最大比赛数。


示例输入 1

6
PRSSRS

示例输出 1

5

在六场剪刀石头布中,青木玩的是布、石头、剪刀、剪刀、石头、剪刀。

高桥可以玩剪刀、布、石头、剪刀、布、石头来赢得第 1、2、3、5 和 6 场比赛。

高桥没有满足条件并赢得全部六场比赛的走法序列,因此打印 5.


示例输入 2

10
SSSSSSSSSS

示例输出 2

5

示例输入 3

24
SPRPSRRRRRPPRPRPSSRSPRSS

示例输出 3

18