103653: [Atcoder]ABC365 D - AtCoder Janken 3

Problem Statement

Takahashi and Aoki played rock-paper-scissors $N$ times. [Note: In this game, Rock beats Scissors, Scissors beats Paper, and Paper beats Rock.]

Aoki's moves are represented by a string $S$ of length $N$ consisting of the characters R, P, and S. The $i$-th character of $S$ indicates Aoki's move in the $i$-th game: R for Rock, P for Paper, and S for Scissors.

Takahashi's moves satisfy the following conditions:

• Takahashi never lost to Aoki.
• For $i=1,2,\ldots,N-1$, Takahashi's move in the $i$-th game is different from his move in the $(i+1)$-th game.

Determine the maximum number of games Takahashi could have won.

It is guaranteed that there exists a sequence of moves for Takahashi that satisfies these conditions.

Constraints

• $1\leq N\leq2\times10 ^ 5$
• $S$ is a string of length $N$ consisting of R, P, and S.
• $N$ is an integer.

Input

The input is given from Standard Input in the following format:

$N$
$S$

Output

Print the maximum number of games Takahashi could have won.

Sample Input 1

6
PRSSRS

Sample Output 1

5

In the six games of rock-paper-scissors, Aoki played Paper, Rock, Scissors, Scissors, Rock, and Scissors.

Takahashi can play Scissors, Paper, Rock, Scissors, Paper, and Rock to win the 1st, 2nd, 3rd, 5th, and 6th games.

There is no sequence of moves for Takahashi that satisfies the conditions and wins all six games, so print $5$.

Sample Input 2

10
SSSSSSSSSS

Sample Output 2

5

Sample Input 3

24
SPRPSRRRRRPPRPRPSSRSPRSS

Sample Output 3

18

问题陈述

高桥和青木玩了N次石头剪刀布。[注意：在这个游戏中，石头胜剪刀，剪刀胜布，布胜石头。]

青木的动作由一个长度为N的字符串S表示，由字符R、P和S组成。 S的第i个字符表示青木在第i局游戏中的动作：R代表石头，P代表布，S代表剪刀。

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

• 高桥从未输给青木。
• 对于i=1,2,…,N-1，高桥在第i局游戏中的动作与他在第(i+1)局游戏中的动作不同。

确定高桥可能赢得的最大游戏局数。

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

约束条件

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

输入

输入从标准输入以下格式给出：

$N$
$S$

输出

打印高桥可能赢得的最大游戏局数。

样本输入 1

6
PRSSRS

样本输出 1

5

在六局石头剪刀布游戏中，青木出了布，石头，剪刀，剪刀，石头，和剪刀。

高桥可以出剪刀，布，石头，剪刀，布，和石头来赢得第1，2，3，5，和第6局游戏。

不存在一个满足条件并能赢得所有六局游戏的动作序列，所以打印5。

样本输入 2

10
SSSSSSSSSS

样本输出 2

5

样本输入 3

24
SPRPSRRRRRPPRPRPSSRSPRSS

样本输出 3

18