問題文

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

入力例 1

4
RSPR

出力例 1

2

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

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

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

入力例 2

3
RSR

出力例 2

0

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

入力例 3

6
SRPPSR

出力例 3

3