問題文

$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$ 人だけになった場合、その人の単独優勝となります。

単独優勝する可能性のある人の人数を求めてください。

制約

• $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$ 点が与えられる。

入力例 1Copy

4
RSPR

出力例 1Copy

2

たとえば次のような手順で大会が行われると、人 $3$ が単独優勝します。

• 人 $1$ と人 $2$ がじゃんけんをして、人 $1$ が勝つ。
• 人 $1$ と人 $3$ がじゃんけんをして、人 $3$ が勝つ。
• 人 $3$ と人 $4$ がじゃんけんをして、人 $3$ が勝つ。

ほかにも、人 $1$ は単独優勝する可能性があります。一方、人 $2$ と人 $4$ は単独優勝する可能性がありません。

入力例 2Copy

3
RSR

出力例 2Copy

0

必ず $2$ 人以上が残ってしまいます。

入力例 3Copy

6
SRPPSR

出力例 3Copy

3